envolvente convexa dinámica

El problema de la envoltura convexa dinámica es una clase de problemas dinámicos en geometría computacional . Consiste en el mantenimiento, es decir, el seguimiento, de la envoltura convexa de datos de entrada que experimentan una secuencia de cambios discretos, es decir, cuando los elementos de los datos de entrada pueden insertarse, eliminarse o modificarse. Debe distinguirse de la envoltura convexa cinética , que estudia problemas similares para puntos en movimiento continuo. Los problemas de la envoltura convexa dinámica se pueden distinguir por los tipos de datos de entrada y los tipos de modificación permitidos de dichos datos.

Es fácil construir un ejemplo en el que la envoltura convexa contiene todos los puntos de entrada, pero después de insertar un solo punto, la envoltura convexa se convierte en un triángulo. Y, a la inversa, la eliminación de un solo punto puede producir el cambio drástico opuesto en el tamaño de la salida. Por lo tanto, si se requiere que la envoltura convexa se reporte de manera tradicional como un polígono, el límite inferior para la complejidad computacional en el peor caso del recálculo de la envoltura convexa es${\displaystyle \Omega (N)}$Dado que este tiempo se requiere para una simple presentación del resultado, este límite inferior es alcanzable, ya que varios algoritmos de envolvente convexa de propósito general se ejecutan en tiempo lineal cuando los puntos de entrada están ordenados de alguna manera, y se conocen métodos de tiempo logarítmico para el mantenimiento dinámico de datos ordenados.

Este problema puede superarse eliminando la restricción en la representación de salida. Existen estructuras de datos que permiten mantener representaciones de la envoltura convexa en un tiempo por actualización mucho menor que el lineal. Durante muchos años, el mejor algoritmo de este tipo fue el de Overmars y van Leeuwen (1981), que requería un tiempo de O(log₂ ⁿ ) por actualización, pero desde entonces ha sido mejorado por Timothy M. Chan y otros.

En diversas aplicaciones, encontrar la envoltura convexa es un paso fundamental en un algoritmo para la solución del problema general. La representación seleccionada de la envoltura convexa puede influir en la complejidad computacional de las operaciones posteriores del algoritmo. Por ejemplo, la consulta de un punto en un polígono convexo representado por el conjunto ordenado de sus vértices puede resolverse en tiempo logarítmico, lo cual sería imposible para envolturas convexas basadas en el conjunto de sus vértices sin información adicional. Por lo tanto, algunas investigaciones sobre algoritmos de envoltura convexa dinámica incluyen la complejidad computacional de diversos problemas de búsqueda geométrica con envolturas convexas almacenadas en estructuras de datos específicas. El enfoque de Overmars y van Leeuwen permite una complejidad logarítmica para diversas consultas comunes.

• Alexandron, Giora; Kaplan, Haim; Sharir, Micha (2005), "Estructuras de datos cinéticas y dinámicas para envolventes convexas y superiores", Algorithms and Data Structures (WADS 2005) , Lecture Notes in Computer Science, vol.  3608, Berlín: Springer, pp. 269–281 , doi : 10.1007/11534273_24 , ISBN  978-3-540-28101-6, MR 2200329 
• Brodal, Gerth Stølting; Jacob, Riko (2000), "Cubierta convexa planar dinámica con tiempo de consulta óptimo y${\displaystyle O(\log n\cdot \log \log n)}$tiempo de actualización", Teoría de algoritmos (SWAT 2000, Bergen) , Lecture Notes in Computer Science, vol.  1851, Berlín: Springer, pp. 57–70 , doi : 10.1007/3-540-44985-X_7 , ISBN  978-3-540-67690-4, MR 1792585 
• Chan, Timothy M. (2001), "Operaciones dinámicas de envolvente convexa planar 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 envolventes convexas 3D y consultas de vecinos más cercanos 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 envolventes convexas dinámicas", 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 ajustados para consultas dinámicas de envolvente convexa (de nuevo)", Actas del Simposio de Geometría Computacional (SoCG 2007) , Nueva York: ACM, pp. 354–363 , doi : 10.1145/1247069.1247131 , ISBN  978-1-59593-705-6, MR 2469185 
• Hershberger, John ; Suri, Subhash (1992), "Aplicaciones de un algoritmo de envolvente convexa semidinámico", BIT , 32 (2): 249–267 , doi : 10.1007/BF01994880 , MR 1172189 
• Oh, Eunjin; Ahn, Hee-Kap (2017), "Envolventes convexas geodésicas dinámicas en polígonos simples dinámicos", 33.º Simposio Internacional sobre Geometría Computacional (SoCG 2017) , LIPIcs, vol.  77, Schloss Dagstuhl, pp.  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.