Algoritmo de Kirkpatrick-Seidel

El algoritmo de Kirkpatrick-Seidel (también conocido como el algoritmo definitivo de envolvente convexa) es un procedimiento diseñado para calcular la envolvente convexa de un conjunto de puntos en el plano, ofreciendo una complejidad temporal de ${\mathcal {O}}(n\log h)$ , donde $n$ es el número de puntos de entrada y $h$ es el número de puntos en la envolvente convexa. Esta complejidad temporal sensible a la salida implica que el tiempo de ejecución del algoritmo depende tanto del tamaño de la entrada como del tamaño de la salida.

Los algoritmos anteriores sensibles a la salida, como el algoritmo de envoltura de regalos, presentaban tiempos de ejecución asintóticos de ${\mathcal {O}}(nh)$ , mientras que los algoritmos no sensibles a la salida se ejecutaban típicamente en tiempo ${\mathcal {O}}(n\log n)$ . El algoritmo de Kirkpatrick-Seidel ofrece una mejora significativa al lograr una cota asintótica más eficiente, lo que lo hace más rápido para ciertos tipos de entrada.

A pesar de su optimalidad teórica, el algoritmo no se utiliza ampliamente en la práctica para conjuntos de datos de tamaño moderado debido a la complejidad de implementación y a las constantes ocultas en la notación asintótica.

Algoritmo

El algoritmo de Kirkpatrick-Seidel es un refinamiento del enfoque clásico de divide y vencerás para el cálculo de envolventes convexas, a menudo descrito como "matrimonio antes de la conquista". En el enfoque tradicional de divide y vencerás, el conjunto de puntos se divide en dos mitades (normalmente mediante una línea vertical), se calcula recursivamente la envolvente convexa de cada mitad y se fusionan las dos envolventes encontrando las aristas de "puente" (bitangentes) que las conectan.

En contraste, el algoritmo de Kirkpatrick-Seidel primero encuentra la mediana de las coordenadas $x$ de los puntos e identifica las aristas de la envolvente convexa que intersecan la línea vertical en esta mediana. Los puntos que no pueden contribuir a la envolvente convexa a ninguno de los lados de la línea mediana se descartan. El algoritmo procede entonces recursivamente sobre los puntos restantes para calcular las partes superior e inferior de la envolvente convexa.

En cada nivel de recursión $i$ , el algoritmo resuelve como máximo $2^{i}$ subproblemas, cada uno con como máximo $n/2^{i}$ puntos. Dado que cada subproblema identifica una única arista de la envolvente convexa, el número total de subproblemas está limitado por $h$ , el número de puntos en la envolvente. En el peor de los casos, cuando no se pueden descartar puntos prematuramente, la profundidad de recursión es ${\mathcal {O}}(\log h)$ , y cada nivel procesa ${\mathcal {O}}(n)$ puntos. Esto resulta en una complejidad temporal total de ${\mathcal {O}}(n\log h)$ .

Desarrollos posteriores

Desde su introducción, el algoritmo de Kirkpatrick-Seidel ha inspirado varios desarrollos tanto en aspectos teóricos como prácticos de los algoritmos de envolvente convexa. En particular, los avances posteriores se han centrado en la optimalidad de instancia y la optimalidad universal.

Optimalidad de instancia: Este concepto se refiere a encontrar algoritmos que sean óptimos para un conjunto específico de instancias, basándose en la distribución y la geometría de los puntos de entrada. Investigaciones recientes han explorado algoritmos que se adaptan a distribuciones de entrada específicas y mejoran dinámicamente el rendimiento en conjuntos de datos típicos.

Optimalidad universal: Este desarrollo busca algoritmos óptimos para todo tipo de entradas, garantizando un rendimiento óptimo en el peor de los casos para una amplia gama de configuraciones de entrada. El algoritmo de Kirkpatrick-Seidel es un firme candidato para la optimización universal en envolventes convexas bidimensionales.

Enfoques cuánticos: Con el auge de la computación cuántica, se han investigado algoritmos cuánticos para envolventes convexas, explorando si los algoritmos cuánticos podrían superar a los métodos clásicos, incluido el algoritmo de Kirkpatrick-Seidel, en casos específicos. Sin embargo, la aceleración cuántica sigue siendo un área de investigación abierta.

Evaluación práctica

Si bien el algoritmo de Kirkpatrick-Seidel es teóricamente óptimo en términos de su complejidad temporal, su aplicabilidad práctica es limitada para conjuntos de datos de tamaño moderado debido a varios factores. El estudio experimental de McQueen y Toussaint reveló que, si bien el algoritmo tuvo un buen desempeño en grandes conjuntos de datos, los factores constantes ocultos en la notación asintótica de ${\mathcal {O}}(n\log h)$ lo hace menos eficiente para instancias pequeñas en comparación con otros algoritmos como el de Chan. El algoritmo de Chan, si bien es asintóticamente menos eficiente en teoría, suele preferirse en la práctica debido a su implementación más sencilla y mejor rendimiento en instancias pequeñas.

Análisis comparativo

En comparación con otros algoritmos de envolvente convexa sensibles a la salida, como el algoritmo de Chan, el algoritmo de Kirkpatrick-Seidel ofrece una mejor cota asintótica ( ${\mathcal {O}}(n\log h)$ frente a ${\mathcal {O}}(nh)$ para el algoritmo de envoltura de regalos y el método de Chan). Sin embargo, el algoritmo de Chan es más práctico debido a su implementación más sencilla, factores constantes más bajos y mejor rendimiento en una amplia gama de conjuntos de datos prácticos. Para problemas de tamaño moderado, el algoritmo de Chan sigue siendo una opción popular, especialmente por su implementación más sencilla y mejores constantes.

Restricciones y problemas abiertos

Aunque el algoritmo de Kirkpatrick-Seidel es teóricamente óptimo, persisten varios problemas tanto en su aplicación práctica como en su expansión teórica:

Complejidad de implementación: La compleja estructura recursiva del algoritmo y su dependencia del cálculo de la mediana de los puntos dificultan su implementación eficiente, especialmente en comparación con otros algoritmos de diseño más sencillo.

Factores constantes: Las constantes ocultas en la complejidad temporal ${\mathcal {O}}(n\log h)$ pueden ralentizar el algoritmo en la práctica para conjuntos de datos de tamaño moderado, limitando su aplicabilidad práctica.

Generalización a altas dimensiones: Si bien el algoritmo es eficiente en dos dimensiones, su generalización a dimensiones superiores presenta importantes desafíos debido a la creciente complejidad del problema de la envolvente convexa en espacios de mayor dimensión.

Algoritmos cuánticos: El potencial de los algoritmos cuánticos para acelerar los cálculos de la envolvente convexa es un área de investigación activa. Sin embargo, aún no se ha demostrado que ningún algoritmo cuántico supere a los algoritmos clásicos como Kirkpatrick-Seidel en escenarios prácticos.

Véase también

Referencias

↑ Kirkpatrick, David G.; Seidel, Raimund (1986). «The ultimate planar convex hull algorithm?». SIAM Journal on Computing 15 (1): 287-299. doi:10.1137/0215021.
1 2 McQueen, Mary M.; Toussaint, Godfried T. (1985). «On the ultimate convex hull algorithm in practice». Pattern Recognition Letters 3 (1): 29-34. doi:10.1016/0167-8655(85)90039-X.
↑ Kirkpatrick, David G.; Seidel, Raimund (1986). «The ultimate planar convex hull algorithm?». SIAM Journal on Computing 15 (1): 10. doi:10.1137/0215021.
↑ Chan, Timothy (2004). «An optimal algorithm for convex hulls in 3D». Journal of the ACM 51 (5). doi:10.1145/1011242.1011256.
1 2 Farhi, Edward (2023). «Quantum algorithms for convex hulls». Quantum Computing 5 (3). doi:10.1137/0215021.
1 2 Chan, Timothy (2004). «Optimal algorithms for convex hulls». SIAM Journal on Computing 33 (6): 1536-1560. doi:10.1137/S0097539701385778.

Datos: Q4060672

[1] Kirkpatrick, David G.; Seidel, Raimund (1986). «The ultimate planar convex hull algorithm?». SIAM Journal on Computing 15 (1): 287-299. doi:10.1137/0215021.

[mcgill-2] 1 2 McQueen, Mary M.; Toussaint, Godfried T. (1985). «On the ultimate convex hull algorithm in practice». Pattern Recognition Letters 3 (1): 29-34. doi:10.1016/0167-8655(85)90039-X.

[3] Kirkpatrick, David G.; Seidel, Raimund (1986). «The ultimate planar convex hull algorithm?». SIAM Journal on Computing 15 (1): 10. doi:10.1137/0215021.

[4] Chan, Timothy (2004). «An optimal algorithm for convex hulls in 3D». Journal of the ACM 51 (5). doi:10.1145/1011242.1011256.

[farhi-5] 1 2 Farhi, Edward (2023). «Quantum algorithms for convex hulls». Quantum Computing 5 (3). doi:10.1137/0215021.

[chan-6] 1 2 Chan, Timothy (2004). «Optimal algorithms for convex hulls». SIAM Journal on Computing 33 (6): 1536-1560. doi:10.1137/S0097539701385778.