Considere el caso general cuando la entrada del algoritmo es un conjunto finito no ordenado de puntos en un plano cartesiano. Un caso especial importante, en el que los puntos se dan en el orden de recorrido de la frontera de un polígono simple, se describe más adelante en una subsección aparte.
Si no todos los puntos están en la misma línea, entonces su casco convexo es un polígono convexo cuyos vértices son algunos de los puntos del conjunto de entrada. Su representación más común es la lista de sus vértices ordenados a lo largo de su frontera en el sentido de las agujas del reloj o en sentido contrario. En algunas aplicaciones es conveniente representar un polígono convexo como una intersección de un conjunto de semiplanos.
Límite inferior de la complejidad computacionalEditar
Para un conjunto finito de puntos en el plano el límite inferior de la complejidad computacional de encontrar el casco convexo representado como un polígono convexo se demuestra fácilmente que es el mismo que para la ordenación utilizando la siguiente reducción. Para el conjunto x 1 , … , x n {{punto de vista x_{1},{punto de vista ,x_{n}}
números para ordenar considere el conjunto de puntos ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
de puntos en el plano. Como se encuentran en una parábola, que es una curva convexa es fácil ver que los vértices del casco convexo, cuando se recorren a lo largo del límite, producen el ordenamiento de los números x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}
. Evidentemente, se requiere un tiempo lineal para la transformación descrita de los números en puntos y luego para extraer su ordenación. Por lo tanto, en el caso general el casco convexo de n puntos no puede ser calculado más rápidamente que la ordenación.
La cota inferior estándar Ω(n log n) para la ordenación se demuestra en el modelo de árbol de decisión de la computación, en el que sólo se pueden realizar comparaciones numéricas pero no operaciones aritméticas; sin embargo, en este modelo, los cascos convexos no se pueden calcular en absoluto. La ordenación también requiere un tiempo Ω(n log n) en el modelo de árbol de decisión algebraico de computación, un modelo que es más adecuado para los cascos convexos, y en este modelo los cascos convexos también requieren un tiempo Ω(n log n). Sin embargo, en los modelos de aritmética computacional que permiten ordenar los números con mayor rapidez que el tiempo O(n log n), por ejemplo mediante el uso de algoritmos de ordenación de enteros, los cascos convexos planares también pueden calcularse con mayor rapidez: el algoritmo de exploración de Graham para los cascos convexos consiste en un único paso de ordenación seguido de una cantidad lineal de trabajo adicional.
Algoritmos óptimos sensibles a la salidaEditar
Como se ha dicho anteriormente, la complejidad de encontrar un casco convexo en función del tamaño de la entrada n está acotada por Ω(n log n). Sin embargo, la complejidad de algunos algoritmos de cascos convexos puede caracterizarse en función tanto del tamaño de entrada n como del tamaño de salida h (el número de puntos del casco). Estos algoritmos se denominan algoritmos sensibles a la salida. Pueden ser asintóticamente más eficientes que los algoritmos Θ(n log n) en los casos en que h = o(n).
El límite inferior del tiempo de ejecución en el peor caso de los algoritmos de cascos convexos sensibles a la salida se estableció en Ω(n log h) en el caso plano. Hay varios algoritmos que alcanzan esta complejidad temporal óptima. El más antiguo fue introducido por Kirkpatrick y Seidel en 1986 (que lo llamaron «el algoritmo de casco convexo definitivo»). Un algoritmo mucho más sencillo fue desarrollado por Chan en 1996, y se denomina algoritmo de Chan.
AlgoritmosEditar
Los algoritmos de casco convexo conocidos se enumeran a continuación, ordenados por la fecha de la primera publicación. La complejidad temporal de cada algoritmo se indica en función del número de puntos de entrada n y del número de puntos del casco h. Obsérvese que, en el peor de los casos, h puede ser tan grande como n.
- Envoltura de regalo, también conocida como marcha de Jarvis – O(nh)
Uno de los algoritmos planares más sencillos (aunque no el más eficiente en términos de tiempo en el peor de los casos). Creado independientemente por Chand & Kapur en 1970 y R. A. Jarvis en 1973. Tiene una complejidad de tiempo O(nh), donde n es el número de puntos en el conjunto, y h es el número de puntos en el casco. En el peor de los casos la complejidad es Θ(n2). - Escaneo de Graham – O(n log n)
Un algoritmo algo más sofisticado, pero mucho más eficiente, publicado por Ronald Graham en 1972. Si los puntos ya están ordenados por una de las coordenadas o por el ángulo respecto a un vector fijo, entonces el algoritmo tarda O(n) tiempo. - Quickhull
Creado independientemente en 1977 por W. Eddy y en 1978 por A. Bykat. Al igual que el algoritmo quicksort, tiene una complejidad temporal esperada de O(n log n), pero puede degenerar a O(n2) en el peor de los casos. - Divide y vencerás – O(n log n)
Otro algoritmo de O(n log n), publicado en 1977 por Preparata y Hong. Este algoritmo también es aplicable al caso tridimensional. - Cadena monótona, también conocido como algoritmo de Andrew- O(n log n)
Publicado en 1979 por A. M. Andrew. El algoritmo puede verse como una variante del barrido de Graham que ordena los puntos lexicográficamente por sus coordenadas. Cuando la entrada ya está ordenada, el algoritmo tarda O(n) de tiempo. - Algoritmo de casco convexo incremental – O(n log n)
Publicado en 1984 por Michael Kallay. - Algoritmo de Kirkpatrick-Seidel – O(n log h)
El primer algoritmo óptimo sensible a la salida. Modifica el algoritmo de divide y vencerás utilizando la técnica del matrimonio antes de la conquista y la programación lineal de baja dimensión. Publicado por Kirkpatrick y Seidel en 1986. - El algoritmo de Chan – O(n log h)
Un algoritmo óptimo sensible a la salida más sencillo creado por Chan en 1996. Combina la envoltura de regalos con la ejecución de un algoritmo O(n log n) (como la exploración de Graham) en pequeños subconjuntos de la entrada.
Heurística de Akl-ToussaintEditar
La siguiente heurística simple se utiliza a menudo como el primer paso en las implementaciones de los algoritmos de cascos convexos para mejorar su rendimiento. Se basa en el eficiente algoritmo del casco convexo de Selim Akl y G. T. Toussaint, 1978. La idea es excluir rápidamente muchos puntos que no formarían parte del casco convexo de todos modos. Este método se basa en la siguiente idea. Encontrar los dos puntos con las coordenadas x más bajas y más altas, y los dos puntos con las coordenadas y más bajas y más altas. (Cada una de estas operaciones requiere O(n)). Estos cuatro puntos forman un cuadrilátero convexo, y todos los puntos que se encuentran en este cuadrilátero (excepto los cuatro vértices elegidos inicialmente) no forman parte del casco convexo. Encontrar todos estos puntos que se encuentran en este cuadrilátero es también O(n), y por lo tanto, toda la operación es O(n). Opcionalmente, los puntos con las sumas más pequeñas y más grandes de las coordenadas x e y, así como aquellos con las diferencias más pequeñas y más grandes de las coordenadas x e y, también pueden añadirse al cuadrilátero, formando así un octógono convexo irregular, cuyos interiores pueden descartarse con seguridad. Si los puntos son variables aleatorias, entonces para una clase estrecha pero comúnmente encontrada de funciones de densidad de probabilidad, este paso de preprocesamiento de desecho hará que un algoritmo de casco convexo se ejecute en tiempo lineal esperado, incluso si la complejidad del peor caso del algoritmo de casco convexo es cuadrática en n.
Problemas de casco convexo en línea y dinámicosEditar
La discusión anterior considera el caso cuando todos los puntos de entrada se conocen de antemano. Uno puede considerar otras dos configuraciones.
- Problema de casco convexo en línea: Los puntos de entrada se obtienen secuencialmente uno por uno. Después de que cada punto llegue a la entrada, el casco convexo para el conjunto de puntos obtenido hasta el momento debe ser calculado eficientemente.
- Mantenimiento dinámico del casco convexo: Los puntos de entrada pueden ser insertados o eliminados secuencialmente, y el casco convexo debe ser actualizado después de cada operación de inserción/eliminación.
La inserción de un punto puede aumentar el número de vértices de un casco convexo como máximo en 1, mientras que la eliminación puede convertir un casco convexo de n vértices en uno de n-1 vértices.
La versión en línea puede ser manejada con O(log n) por punto, lo que es asintóticamente óptimo. La versión dinámica puede manejarse con O(log2 n) por operación.
Polígono simpleEditar
El casco convexo de un polígono simple está dividido por el polígono en trozos, uno de los cuales es el propio polígono y el resto son bolsas delimitadas por un trozo del límite del polígono y una única arista del casco. Aunque se han publicado muchos algoritmos para el problema de construir el casco convexo de un polígono simple, casi la mitad de ellos son incorrectos.McCallum y Avis proporcionaron el primer algoritmo correcto.Una simplificación posterior de Graham & Yao (1983) y Lee (1983) utiliza sólo una estructura de datos de pila única. Su algoritmo recorre el polígono en el sentido de las agujas del reloj, empezando por su vértice más a la izquierda. Mientras lo hace, almacena una secuencia convexa de vértices en la pila, los que aún no han sido identificados como dentro de las bolsas. En cada paso, el algoritmo sigue un camino a lo largo del polígono desde el tope de la pila hasta el siguiente vértice que no está en una de las dos bolsas adyacentes al tope de la pila. A continuación, mientras los dos vértices superiores de la pila junto con este nuevo vértice no estén en posición convexa, hace saltar la pila, antes de empujar finalmente el nuevo vértice a la pila. Cuando el recorrido en el sentido de las agujas del reloj llega al punto de partida, el algoritmo devuelve la secuencia de vértices de la pila como el casco.