El problema del casco convexo dinámico es una clase de problemas dinámicos en geometría computacional . El problema consiste en el mantenimiento, es decir, el seguimiento del casco convexo para los datos de entrada que experimentan una secuencia de cambios discretos, es decir, cuando los elementos de datos de entrada pueden insertarse, eliminarse o modificarse. Debe distinguirse del casco cinético convexo , que estudia problemas similares para puntos en continuo movimiento. Los problemas dinámicos del casco convexo se pueden distinguir por los tipos de datos de entrada y los tipos permitidos de modificación de los datos de entrada.
Conjunto de puntos planos
Es fácil construir un ejemplo en el que el casco convexo contenga todos los puntos de entrada, pero después de la inserción de un solo punto, el casco convexo se convierte en un triángulo. Y a la inversa, la eliminación de un solo punto puede producir el cambio drástico opuesto del tamaño de la salida. Por lo tanto, si se requiere que el casco convexo se informe de la manera tradicional como un polígono, el límite inferior para la complejidad computacional del peor de los casos del recálculo del casco convexo es, ya que este tiempo es necesario para un simple informe de la salida. Este límite inferior es alcanzable, porque varios algoritmos de casco convexo de propósito general se ejecutan en tiempo lineal cuando los puntos de entrada están ordenados de alguna manera y los métodos de tiempo logarítmico para el mantenimiento dinámico de datos ordenados son bien conocidos.
Este problema puede superarse eliminando la restricción en la representación de salida. Hay estructuras de datos que pueden mantener representaciones del casco convexo en una cantidad de tiempo por actualización mucho menor que lineal. Durante muchos años, el mejor algoritmo de este tipo fue el de Overmars y van Leeuwen (1981), que tomó tiempo O (log 2 n ) por actualización, pero desde entonces ha sido mejorado por Timothy M. Chan y otros.
En varias aplicaciones, encontrar el casco convexo es un paso en un algoritmo para la solución del problema general. La representación seleccionada del casco convexo puede influir en la complejidad computacional de operaciones adicionales del algoritmo general. Por ejemplo, la consulta de punto en polígono para un polígono convexo representado por el conjunto ordenado de sus vértices puede responderse en tiempo logarítmico, lo que sería imposible para cascos convexos informados por el conjunto de sus vértices sin ninguna información adicional. Por lo tanto, algunas investigaciones de algoritmos dinámicos de cascos convexos implican la complejidad computacional de varios problemas de búsqueda geométrica con cascos convexos almacenados en tipos específicos de estructuras de datos. El enfoque mencionado de Overmars y van Leeuwen permite la complejidad logarítmica de varias consultas comunes.
Referencias
- Alexandron, Giora; Kaplan, Haim; Sharir, Micha (2005), "Estructuras de datos cinéticas y dinámicas para cascos convexos y envolventes superiores", Algoritmos y estructuras de datos (WADS 2005) , Lecture Notes in Computer Science, 3608 , Berlín: Springer, págs. 269-281, doi : 10.1007 / 11534273_24 , MR 2200329
- Brodal, Gerth Stølting; Jacob, Riko (2000), "Casco convexo plano dinámico con tiempo de consulta óptimo ytiempo de actualización ", Algorithm Theory (SWAT 2000, Bergen) , Lecture Notes in Computer Science, 1851 , Berlín: Springer, págs. 57–70, doi : 10.1007 / 3-540-44985-X_7 , MR 1792585
- Chan, Timothy M. (2001), "Operaciones dinámicas de casco convexo plano en tiempo amortizado casi logarítmico", Journal of the ACM , 48 (1): 1–12, doi : 10.1145 / 363647.363652 , MR 1867273
- Chan, Timothy M. (2010), "Una estructura de datos dinámica para cascos convexos en 3D y consultas de vecinos más cercanos en 2D", Journal of the ACM , 57 (3): A16: 1 – A16: 15, doi : 10.1145 /1706591.1706596 , MR 2665885
- Chan, Timothy M. (2012), "Tres problemas sobre cascos convexos dinámicos", International Journal of Computational Geometry & Applications , 22 (4): 341–364, doi : 10.1142 / S0218195912600096 , MR 2994585
- Demaine, Erik D .; Pǎtraşcu, Mihai (2007), " Límites estrechos para consultas dinámicas de casco convexo (nuevamente)", Proc. Symp. Geometría computacional (SoCG 2007) , Nueva York: ACM, págs. 354–363, doi : 10.1145 / 1247069.1247131 , MR 2469185
- Hershberger, John ; Suri, Subhash (1992), "Aplicaciones de un algoritmo de casco convexo semidinámico", BIT , 32 (2): 249-267, doi : 10.1007 / BF01994880 , MR 1172189
- Oh, Eunjin; Ahn, Hee-Kap (2017), "Cascos convexos geodésicos dinámicos en polígonos simples dinámicos", 33 ° Simposio Internacional sobre Geometría Computacional (SoCG 2017) , LIPIcs, 77 , Schloss Dagstuhl, págs. 51: 1–51: 15, doi : 10.4230 / LIPIcs.SoCG.2017.51 , MR 3685723
- Overmars, MH ; van Leeuwen, J. (1981), "Mantenimiento de configuraciones en el plano", Journal of Computer and System Sciences , 23 (2): 166-204, doi : 10.1016 / 0022-0000 (81) 90012-X.