Algoritmos de envoltura convexa

Los algoritmos que construyen envolturas convexas de diversos objetos tienen una amplia gama de aplicaciones en matemáticas y ciencias de la computación .

En geometría computacional , se proponen numerosos algoritmos para calcular la envoltura convexa de un conjunto finito de puntos, con diversas complejidades computacionales .

El cálculo de la envoltura convexa permite construir una representación no ambigua y eficiente de la forma convexa requerida. La complejidad de los algoritmos correspondientes se estima generalmente en términos de n , el número de puntos de entrada, y a veces también en términos de h , el número de puntos en la envoltura convexa.

Consideremos el caso general en el que la entrada del algoritmo es un conjunto finito y desordenado de puntos en un plano cartesiano. Un caso especial importante, en el que los puntos se dan en el orden en que se atraviesa el límite 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 envoltura convexa 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 límite 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 .

Para un conjunto finito de puntos en el plano, se demuestra fácilmente que el límite inferior de la complejidad computacional para encontrar la envoltura convexa representada como un polígono convexo es el mismo que para la ordenación utilizando la siguiente reducción . Para el conjunto de números a ordenar, considere el conjunto de puntos en el plano. Dado que se encuentran en una parábola , que es una curva convexa , es fácil ver que los vértices de la envoltura convexa, cuando se recorren a lo largo del límite, producen el orden ordenado de los números . Claramente, se requiere tiempo lineal para la transformación descrita de números en puntos y luego extraer su orden ordenado. Por lo tanto, en el caso general, la envoltura convexa de n puntos no se puede calcular más rápidamente que la ordenación. ${\displaystyle x_{1},\puntos ,x_{n}}$${\displaystyle (x_{1},x_{1}^{2}),\puntos ,(x_{n},x_{n}^{2})}$${\displaystyle x_{1},\puntos ,x_{n}}$

El límite inferior estándar Ω( n log n ) para la ordenación se prueba en el modelo de árbol de decisión de computación, en el que solo se pueden realizar comparaciones numéricas pero no operaciones aritméticas; sin embargo, en este modelo, las envolturas convexas 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 envolturas convexas, y en este modelo las envolturas convexas también requieren un tiempo Ω( n log n ). ^[1] Sin embargo, en modelos de aritmética informática que permiten ordenar números más rápidamente que el tiempo O ( n log n ), por ejemplo mediante el uso de algoritmos de ordenación de números enteros , las envolturas convexas planas también se pueden calcular más rápidamente: el algoritmo de escaneo de Graham para envolturas convexas consiste en un solo paso de ordenación seguido de una cantidad lineal de trabajo adicional.

Como se indicó anteriormente, la complejidad de encontrar una envoltura convexa en función del tamaño de entrada n está limitada inferiormente por Ω( n log n ). Sin embargo, la complejidad de algunos algoritmos de envoltura convexa se puede caracterizar en términos tanto del tamaño de entrada n como del tamaño de salida h (la cantidad de puntos en la envoltura). Dichos 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 de los casos de los algoritmos de envoltura convexa sensibles a la salida se estableció en Ω( n log h ) en el caso planar. ^[1] Hay varios algoritmos que alcanzan esta complejidad temporal óptima . El primero fue introducido por Kirkpatrick y Seidel en 1986 (quienes lo llamaron "el algoritmo de envoltura convexa definitivo "). Chan desarrolló un algoritmo mucho más simple en 1996, y se llama algoritmo de Chan .

A continuación se enumeran los algoritmos de envoltura convexa conocidos, ordenados por fecha de primera publicación. La complejidad temporal de cada algoritmo se expresa en términos de la cantidad de puntos de entrada n y la cantidad de puntos en la envoltura h . Tenga en cuenta que, en el peor de los casos, h puede ser tan grande como n .

• Envoltura de regalos , también conocida como marcha de Jarvis — O ( nh )
  Uno de los algoritmos planares más simples (aunque no el más eficiente en el tiempo en el peor de los casos). Creado independientemente por Chand y Kapur en 1970 y RA Jarvis en 1973. Tiene una complejidad temporal de 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 O ( n ² ).
• Exploración de Graham — O ( n log n )
  Un algoritmo ligeramente 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 con 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 ( n ² ) en el peor de los casos.
• Divide y vencerás — O ( n log n )
  Otro algoritmo 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 conocida como algoritmo de Andrew : O ( n log n )
  Publicado en 1979 por AM Andrew. El algoritmo puede considerarse una variante del escaneo de Graham que ordena los puntos lexicográficamente por sus coordenadas. Cuando la entrada ya está ordenada, el algoritmo tarda O ( n ) tiempo.
• Algoritmo de envoltura convexa 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 de matrimonio antes de conquistar y programación lineal de baja dimensión . Publicado por Kirkpatrick y Seidel en 1986.
• Algoritmo de Chan : O ( n log h )
  Un algoritmo sensible a la salida óptima más simple creado por Chan en 1996. Combina el envoltorio de regalo con la ejecución de un algoritmo O ( n log n ) (como el escaneo de Graham) en pequeños subconjuntos de la entrada.

La siguiente heurística simple se utiliza a menudo como el primer paso en las implementaciones de algoritmos de envoltura convexa para mejorar su rendimiento. Se basa en el algoritmo de envoltura convexa eficiente de Selim Akl y GT Toussaint , 1978. La idea es excluir rápidamente muchos puntos que de todos modos no serían parte de la envoltura convexa. Este método se basa en la siguiente idea. Encuentre 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 toma 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 son parte de la envoltura convexa. Encontrar todos estos puntos que se encuentran en este cuadrilátero también es O( n ), y por lo tanto, la operación completa 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 se pueden agregar al cuadrilátero, formando así un octógono convexo irregular, cuyos interiores se pueden descartar de manera segura. 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 descartable hará que un algoritmo de envoltura convexa se ejecute en un tiempo esperado lineal, incluso si la complejidad del peor caso del algoritmo de envoltura convexa es cuadrática en n . ^[2]

El análisis anterior considera el caso en el que todos los puntos de entrada se conocen de antemano. Se pueden considerar otras dos situaciones. ^[1]

• Problema de envoltura convexa en línea : los puntos de entrada se obtienen secuencialmente uno por uno. Después de que cada punto llega a la entrada, se debe calcular de manera eficiente la envoltura convexa para el conjunto de puntos obtenido hasta el momento.
• Mantenimiento de la envoltura convexa dinámica : los puntos de entrada se pueden insertar o eliminar secuencialmente, y la envoltura convexa se debe actualizar 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 una envoltura convexa en como máximo 1, mientras que la eliminación puede convertir una envoltura convexa de n vértices en una de n-1 vértices.

La versión en línea puede manejarse con O(log n ) por punto, lo que es asintóticamente óptimo. La versión dinámica puede manejarse con O(log ² n ) por operación. ^[1]

La envoltura convexa de un polígono simple está dividida por el polígono en partes, una de las cuales es el polígono mismo y el resto son bolsillos delimitados por una parte del límite del polígono y un solo borde de la envoltura. Aunque se han publicado muchos algoritmos para el problema de construir la envoltura convexa de un polígono simple, casi la mitad de ellos son incorrectos. ^[3] McCallum y Avis proporcionaron el primer algoritmo correcto. ^[4] Una simplificación posterior de Graham & Yao (1983) y Lee (1983) utiliza solo una única estructura de datos de pila . Su algoritmo recorre el polígono en el sentido de las agujas del reloj, comenzando desde 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 se han identificado como dentro de los bolsillos. En cada paso, el algoritmo sigue un camino a lo largo del polígono desde la parte superior de la pila hasta el siguiente vértice que no está en uno de los dos bolsillos adyacentes a la parte superior de la pila. Luego, mientras los dos vértices superiores de la pila junto con este nuevo vértice no están en posición convexa, hace estallar la pila, antes de finalmente empujar el nuevo vértice hacia la pila. Cuando el recorrido en el sentido de las agujas del reloj llega al punto de inicio, el algoritmo devuelve la secuencia de vértices de la pila como la envoltura. ^{[5] [6]}

Se conocen varios algoritmos para el caso tridimensional, así como para dimensiones arbitrarias. ^[7] El algoritmo de Chan se utiliza para las dimensiones 2 y 3, y Quickhull se utiliza para el cálculo de la envoltura convexa en dimensiones superiores. ^[8]

Para un conjunto finito de puntos, la envoltura convexa es un poliedro convexo en tres dimensiones, o en general un politopo convexo para cualquier número de dimensiones, cuyos vértices son algunos de los puntos del conjunto de entrada. Sin embargo, su representación no es tan simple como en el caso plano. En dimensiones superiores, incluso si se conocen los vértices de un politopo convexo, la construcción de sus caras es una tarea no trivial, como lo es el doble problema de construir los vértices dadas las caras. El tamaño de la información de la cara de salida puede ser exponencialmente mayor que el tamaño de los vértices de entrada, e incluso en casos en los que la entrada y la salida son ambas de tamaño comparable, los algoritmos conocidos para envolturas convexas de alta dimensión no son sensibles a la salida debido tanto a problemas con entradas degeneradas como con resultados intermedios de alta complejidad. ^[9]

• Envolvente convexa ortogonal

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sección 33.3: Hallazgo de la envoltura convexa, págs. 947–957. 
• Franco P. Preparata , SJ Hong. Envolturas convexas de conjuntos finitos de puntos en dos y tres dimensiones , Commun. ACM, vol. 20, núm. 2, págs. 87–93, 1977.
• Marcos de Berg ; Marc van Kreveld ; Mark Overmars y Otfried Schwarzkopf (2000). Geometría computacional (2ª edición revisada). Springer-Verlag . ISBN 978-3-540-65620-3.Sección 1.1: Un ejemplo: Envolturas convexas (describe algoritmos clásicos para envolturas convexas bidimensionales). Capítulo 11: Envolturas convexas: págs. 235-250 (describe un algoritmo aleatorio para envolturas convexas tridimensionales creado por Clarkson y Shor).

• Weisstein, Eric W. "Casco convexo". MathWorld .
• Envolvente convexa 2D, 3D y dD en CGAL , la biblioteca de algoritmos de geometría computacional
• Código Qhull para envoltura convexa, triangulación de Delaunay, diagrama de Voronoi e intersección de semiespacios
• Demostración como Flash swf, algoritmos Jarvis, Graham, Quick (divide y vencerás) y Chan
• Algoritmo de envoltura de regalos en C#