Los algoritmos que obtienen la envolvente convexa de diversos objetos tienen un amplio campo de utilización en matemáticas y ciencias de la computación.

En geometría computacional se dispone de numerosos algoritmos para calcular la envolvente convexa de un conjunto finito de puntos, con diversas complejidades computationales.

Calcular la envolvente convexa implica construir una representación no ambigua y eficiente con la forma convexa requerida. La complejidad de los algoritmos correspondientes se suele estimar en función de n, el número de puntos considerados, y a veces también en función de h, el número de puntos en la envolvente convexa.

Caso plano Considérese el caso general en el que la entrada al algoritmo es un conjunto finito y no ordenado de puntos en un plano cartesiano. Un caso especial importante, en el que los puntos se dan en el orden de recorrido del contorno 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 recta, su envolvente 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 en su contorno en sentido horario o antihorario. En algunas aplicaciones, resulta conveniente representar un polígono convexo como la intersección de un conjunto de semiplanos.

Límite inferior de la complejidad computacional Para un conjunto finito de puntos en el plano, se demuestra fácilmente que el límite inferior de la complejidad computacional para hallar la envolvente convexa representada como un polígono convexo es el mismo que el resultante para ordenarlos utilizando la reducción siguiente. Para ordenar el conjunto de números , se debe considerar el conjunto de puntos en el plano. Dado que el contorno de estos valores elevados al cuadrado se encuentra sobre una parábola, que es un curva convexa, es fácil ver que los vértices de la envolvente convexa, al recorrerlos en el contorno, producen la ordenación de los números . Es evidente que se requiere complejidad lineal para la transformación descrita de números en puntos y la posterior extracción de su ordenación. Por lo tanto, en el caso general, la envolvente convexa de puntos no puede calcularse más rápidamente que la ordenación.

El límite inferior estándar para la ordenación se demuestra con un 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 envolventes convexas no se pueden calcular en absoluto. La ordenación también requiere un tiempo en el modelo de árbol de decisión de computación, un modelo más adecuado para las envolventes convexas, y en este modelo las envolventes convexas también requieren un tiempo .Preparata, Shamos, Computational Geometry, Chapter "Convex Hulls: Basic Algorithms" Sin embargo, en modelos de aritmética computacional que permiten ordenar números más rápidamente que el tiempo , por ejemplo, mediante algoritmos de ordenación de enteros, las envolventes convexas planas también se pueden calcular más rápidamente: el algoritmo del método de Graham para envolventes convexas consiste en un único paso de ordenación seguido de una cantidad lineal de trabajo adicional.

Algoritmos óptimos sensibles a la salida Como se indicó anteriormente, la complejidad de encontrar una envolvente convexa en función del tamaño de entrada está limitada inferiormente por . Sin embargo, la complejidad de algunos algoritmos de envolvente convexa se puede caracterizar en términos tanto del tamaño de entrada como del tamaño de salida (el número de puntos en la envolvente). Dichos algoritmos se denominan algoritmos sensibles a la salida. Pueden ser asintóticamente más eficientes que los algoritmos en casos donde .

El límite inferior del tiempo de ejecución en el peor caso de los algoritmos de envolvente convexa sensibles a la salida se estableció en en el caso plano. Existen varios algoritmos que alcanzan este óptimo de complejidad temporal. El primero fue introducido por Kirkpatrick y Seidel en 1986 (quien lo denominó el algoritmo definitivo de envolvente convexa). Un algoritmo mucho más simple fue desarrollado por Chan en 1996 y se denomina el algoritmo de Chan.

Algoritmos

Los algoritmos de envolvente convexa conocidos se enumeran a continuación, ordenados por fecha de primera publicación. La complejidad temporal de cada algoritmo se expresa en términos del número de puntos de entrada y el número de puntos en la envolvente . Nótese que en el peor caso, puede ser tan grande como .

Envoltura de regalos, también conocido como marcha de Jarvis — O(nh) Uno de los algoritmos para el plano más simples (aunque no el más eficiente en el peor de los casos). Creado independientemente por Chand y Kapur en 1970 y R. A. Jarvis en 1973. Tiene complejidad temporal O(nh), donde n es el número de puntos en el conjunto y h es el número de puntos en la envolvente. En el peor de los casos, la complejidad es O(n2).

Método de Graham — O(n log n) Un algoritmo ligeramente más sofisticado, pero mucho más eficiente. Algoritmo 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, el algoritmo requiere un tiempo de O(n).

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, también conocido como fusión de contornos — 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. Chan lo denomina "una de las mejores ilustraciones del poder del paradigma de divide y vencerás". Monotone chain, también conocido como algoritmo de Andrew — O(n log n) Publicado en 1979 por A. M. Andrew. El algoritmo puede considerarse una variante del método de Graham, que ordena los puntos lexicográficamente según sus coordenadas. Cuando la entrada ya está ordenada, el algoritmo requiere un tiempo de O(n).

Algoritmo incremental de la envolvente convexa — 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 la conquista y la programación lineal de baja dimensión. Publicado por Kirkpatrick y Seidel en 1986.

Algoritmo de Chan — O(n log h) Un algoritmo óptimo más simple sensible a la salida, creado por Chan en 1996. Combina la técnica de la envoltura de regalos con la ejecución de un algoritmo O(n log n) (como el modelo de Graham) en pequeños subconjuntos de la entrada.

Heurística de Aklöussaint

La siguiente heurística simple se usa a menudo como primer paso en el desarrollo de algoritmos de envolvente convexa para mejorar su rendimiento. Se basa en el eficiente algoritmo de envolvente convexa de Selim Akl y G. T. Toussaint, de 1978. La idea es excluir rápidamente muchos puntos que de todos modos no formarían parte de la envolvente convexa. 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 un tiempo 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 de la envolvente convexa. Encontrar todos estos puntos que se encuentran en este cuadrilátero también es O(n) y, por tanto, toda la operación es O(n). Opcionalmente, los puntos con sumas más pequeñas y más grandes de coordenadas x e y, así como aquellos con diferencias más pequeñas y más grandes de coordenadas x e y, también se pueden agregar al cuadrilátero, formando así un octágono convexo irregular, cuyo interior se puede descartar con seguridad. Si los puntos son variables aleatorias, entonces para una clase estrecha pero común de funciones de densidad de probabilidad, este paso de preprocesamiento "desechable" hará que un algoritmo de envolvente convexa se ejecute en el tiempo esperado lineal, incluso si la complejidad del peor de los casos del algoritmo de envolvente convexa es cuadrática en n.Luc Devroye y Godfried Toussaint, "A note on linear expected time algorithms for finding convex hulls," Computing, Vol. 26, 1981, pp. 361-366.

Problemas de envolvente convexa dinámico y en línea La discusión anterior considera el caso en el que todos los puntos de entrada se conocen de antemano. Se pueden considerar otros dos escenarios.

Problema de envolvente 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 envolvente convexa para el conjunto de puntos obtenido hasta ahora. Mantener una envolvente convexa dinámica: los puntos de entrada pueden insertarse o eliminarse secuencialmente, y la envolvente convexa debe actualizarse 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 envolvente convexa como máximo en 1, mientras que la eliminación puede convertir un envolvente convexa de n-vértices en uno de n-1-vértices.

La versión en línea puede manejarse con O(log n) por punto, lo cual es asintóticamente óptimo. La versión dinámica se puede manejar con O(log2 n) por operación.

Polígono simple

La envolvente 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 una sola arista de la envolvente. Aunque se han publicado muchos algoritmos para el problema de construir la envolvente convexa de un polígono simple, casi la mitad de ellos son incorrectos. McCallum y Avis proporcionaron el primer algoritmo correcto. Una simplificación posterior realizada por y utiliza solo una pila de datos. Su algoritmo atraviesa 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, aquellos que aún no han sido identificados como dentro de los bolsillos. En cada paso, el algoritmo sigue una ruta en el 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 inicial, el algoritmo devuelve la secuencia de vértices de la pila como casco.

Dimensiones superiores Se conocen varios algoritmos tanto para el caso tridimensional como para dimensiones arbitrarias.Véase David Mount's Lecture Notes, incluyendo Lectura 4 para los desarrollos recientes, incluyendo el algoritmo de Chan. El algoritmo de Chan se utiliza para las dimensiones 2 y 3, y el Quickhull se utiliza para calcular la envolvente convexa en dimensiones superiores.