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.
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 .
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 . [3]
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]
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 2 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. [4] McCallum y Avis proporcionaron el primer algoritmo correcto. [5] 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. [6] [7]
Se conocen varios algoritmos para el caso tridimensional, así como para dimensiones arbitrarias. [8] 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. [9]
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 problema dual 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. [10]
