Algoritmo de Kirkpatrick-Seidel

El algoritmo de Kirkpatrick-Seidel es un algoritmo diseñado para calcular la envoltura convexa de un conjunto de puntos en el plano, ofreciendo una complejidad temporal de${\displaystyle {\mathcal {O}}(n\log h)}$, dónde${\displaystyle n}$es el número de puntos de entrada y${\displaystyle h}$es el número de puntos en la envoltura convexa. ^{[ 1 ]} 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 , exhibieron tiempos de ejecución asintóticos de${\displaystyle {\mathcal {O}}(nh)}$, mientras que los algoritmos no sensibles a la salida normalmente se ejecutaban en${\displaystyle {\mathcal {O}}(n\log n)}$tiempo. 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 la implementación y las constantes ocultas en la notación asintótica. ^{[ 2 ]}

El algoritmo de Kirkpatrick-Seidel es un perfeccionamiento del método clásico de divide y vencerás para calcular envolventes convexas, a menudo descrito como "un matrimonio antes de la conquista". En el método 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 las dos envolventes se unen encontrando las aristas "puente" (bitangentes) que las conectan.

En cambio, el algoritmo de Kirkpatrick-Seidel primero encuentra la mediana de los puntos.${\displaystyle x}$-coordena e identifica los bordes de la envoltura convexa que intersecan la línea vertical en esta mediana. ^{[ 3 ]} Los puntos que no pueden contribuir a la envoltura convexa a ambos 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 envoltura convexa.

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

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

Optimalidad de instancia: Este concepto se refiere a la búsqueda de algoritmos ó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. ^{[ 4 ]}

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 realizado investigaciones sobre algoritmos cuánticos para envolventes convexas, explorando si estos algoritmos 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. ^{[ 5 ]}

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 ^{[ 6 ]} reveló que, si bien el algoritmo funcionó bien en conjuntos de datos grandes, los factores constantes ocultos en la notación asintótica de${\displaystyle {\mathcal {O}}(n\log h)}$lo hace menos eficiente para instancias más pequeñas en comparación con otros algoritmos como el de Chan. ^{[ 7 ]} El algoritmo de Chan, aunque asintóticamente menos eficiente en teoría, a menudo se prefiere en la práctica debido a su implementación más simple y mejor rendimiento en instancias más pequeñas.

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 (${\displaystyle {\mathcal {O}}(n\log h)}$versus${\displaystyle {\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 simple, 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. ^{[ 8 ]}

Si bien el algoritmo de Kirkpatrick-Seidel es teóricamente óptimo, aún quedan varias cuestiones abiertas 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 de la búsqueda 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${\displaystyle {\mathcal {O}}(n\log h)}$Esto puede ralentizar el algoritmo en la práctica para conjuntos de datos de tamaño moderado, lo que limita su aplicabilidad práctica.

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

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, ningún algoritmo cuántico ha demostrado aún superar a los algoritmos clásicos como Kirkpatrick-Seidel en escenarios prácticos. ^{[ 9 ]}

• Algoritmos de envolvente convexa
• Algoritmo de envoltura de regalos
• El algoritmo de Chan