Los algoritmos que construyen cascos convexos de varios objetos tienen una amplia gama de aplicaciones en matemáticas e informática .
En geometría computacional , se proponen numerosos algoritmos para calcular el casco convexo de un conjunto finito de puntos, con diversas complejidades computacionales .
Calcular el casco convexo significa que se construye una representación no ambigua y eficiente de la forma convexa requerida. La complejidad de los algoritmos correspondientes generalmente se estima 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 el casco convexo.
Caso plano
Considere el caso general cuando la entrada al algoritmo es un conjunto finito desordenado de puntos en un plano cartesiano. Un caso especial importante, en el que los puntos se dan en el orden de recorrido del límite de un polígono simple, se describe más adelante en una subsección separada.
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 en el 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 sentido horario o antihorario. En algunas aplicaciones, es conveniente representar un polígono convexo como una intersección de un conjunto de semiplanos .
Límite inferior de complejidad computacional
Para un conjunto finito de puntos en el plano, se muestra fácilmente que el límite inferior de la complejidad computacional de encontrar el casco convexo representado como un polígono convexo es el mismo que para la clasificación utilizando la siguiente reducción . Para el set números para ordenar considerar el conjunto de puntos 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 del casco convexo, cuando se atraviesan 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, el casco convexo de n puntos no se puede calcular más rápidamente que la clasificación.
El límite inferior estándar Ω ( n log n ) para la clasificación se prueba en el modelo de árbol de decisión de la computación, en el que solo 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 clasificación también requiere Ω ( n log n ) tiempo en el modelo de cálculo de árbol de decisión algebraico , un modelo que es más adecuado para cascos convexos, y en este modelo los cascos convexos también requieren Ω ( n log n ) tiempo. [1] Sin embargo, en los modelos de aritmética informática que permiten clasificar los números más rápidamente que el tiempo O ( n log n ), por ejemplo, mediante el uso de algoritmos de clasificación de enteros , los cascos convexos planos también se pueden calcular más rápidamente: el algoritmo de escaneo de Graham para Los cascos convexos consisten en un solo paso de clasificación seguido de una cantidad lineal de trabajo adicional.
Algoritmos óptimos sensibles a la salida
Como se indicó anteriormente, la complejidad de encontrar un casco convexo en función del tamaño de entrada n es menor delimitada por Ω ( n log n ). Sin embargo, la complejidad de algunos algoritmos de casco convexo se puede caracterizar tanto en términos de tamaño de entrada n como de tamaño de salida h (el número de puntos en el 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 de los casos de los algoritmos de casco convexo sensibles a la salida se estableció en Ω ( n log h ) en el caso plano. [1] Hay varios algoritmos que logran esta complejidad de tiempo óptima . El primero fue introducido por Kirkpatrick y Seidel en 1986 (quienes lo llamaron "el algoritmo de casco convexo definitivo "). Chan desarrolló un algoritmo mucho más simple en 1996, y se llama algoritmo de Chan .
Algoritmos
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 expresa en términos del número de puntos de entrada n y el número de puntos en el casco h . Tenga en cuenta que, en el peor de los casos, h puede ser tan grande como n .
- Envoltorio de regalo , también conocido como Jarvis march - O ( nh )
Uno de los algoritmos planos más simples (aunque no el más eficiente en el peor de los casos). Creado independientemente por Chand & Kapur en 1970 y RA 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 Θ ( n 2 ). - Escaneo de Graham - O ( n log n )
Un algoritmo un poco 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 de un vector fijo, entonces el algoritmo toma O ( n ) tiempo. - Quickhull
Creado de forma independiente en 1977 por W. Eddy y en 1978 por A. Bykat. Al igual que elalgoritmo de ordenación rápida , tiene la complejidad de tiempo esperada de O ( n log n ), pero puede degenerar a O ( n 2 ) en el peor de los casos. - Divide y vencerás - O ( n log n )
OtroalgoritmoO ( 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 verse como 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 incremental de casco convexo - 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. - Algoritmo de Chan - O ( n log h )
Un algoritmo sensible a la salida óptimo más simple creado por Chan en 1996. Combina el envoltorio para regalo con la ejecución de unalgoritmo O ( n log n ) (como el escaneo de Graham) en pequeños subconjuntos de la entrada .
Akl – Toussaint heurística
La siguiente heurística simple se usa a menudo como el primer paso en la implementación de algoritmos de casco convexo para mejorar su desempeño. Se basa en el eficiente algoritmo de casco convexo de Selim Akl y GT Toussaint , 1978. La idea es excluir rápidamente muchos puntos que de todos modos no formarían parte del casco convexo. 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 forman parte del casco convexo. Encontrar todos estos puntos que se encuentran en este cuadrilátero también es O ( n ) y, por lo tanto, toda la operación es O ( n ). Opcionalmente, los puntos con sumas más pequeñas y más grandes de coordenadas xey, así como aquellos con diferencias más pequeñas y más grandes de coordenadas xey también se pueden agregar al cuadrilátero, formando así un octágono convexo irregular, cuyo interior puede ser desechado de forma segura. 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 casco convexo se ejecute en el tiempo lineal esperado, incluso si la complejidad del peor de los casos es convexa. El algoritmo de casco es cuadrático en n . [2]
Problemas de casco convexo 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. [1]
- Problema de casco convexo en línea : los puntos de entrada se obtienen secuencialmente uno por uno. Después de que cada punto llega a la entrada, el casco convexo para el conjunto de puntos obtenido hasta ahora debe calcularse de manera eficiente.
- Mantenimiento dinámico del casco convexo : los puntos de entrada pueden insertarse o eliminarse secuencialmente, y el casco convexo 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 un casco convexo como máximo por 1, mientras que la deleción puede convertir un n -vertex convexa casco en un n-1 -vertex uno.
La versión online puede manejarse con O (log n ) por punto, que es asintóticamente óptimo. La versión dinámica se puede manejar con O (log 2 n ) por operación. [1]
Polígono simple
El casco convexo de un polígono simple está dividido 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 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. [3] McCallum y Avis proporcionaron el primer algoritmo correcto. [4] Una simplificación posterior de Graham y Yao (1983) y Lee (1983) utiliza sólo una estructura de datos de una sola pila . 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, los que aún no se han identificado como dentro de los bolsillos. En cada paso, el algoritmo sigue una ruta 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 sentido horario alcanza el punto de inicio, el algoritmo devuelve la secuencia de vértices de la pila como el casco. [5] [6]
Mayores dimensiones
Se conocen varios algoritmos para el caso tridimensional, así como para dimensiones arbitrarias. [7] El algoritmo de Chan se usa para las dimensiones 2 y 3, y Quickhull se usa para calcular el casco convexo en dimensiones más altas. [8]
Para un conjunto finito de puntos, el casco convexo 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 no es una tarea 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 los casos en que la entrada y la salida son de tamaño comparable, los algoritmos conocidos para cascos convexos de alta dimensión no son sensibles a la salida debido a que problemas con insumos degenerados y con resultados intermedios de alta complejidad. [9]
Ver también
- Casco convexo ortogonal
Referencias
- ^ a b c d Preparata, Shamos, geometría computacional , capítulo "Cascos convexos: algoritmos básicos"
- ^ Luc Devroye y Godfried Toussaint , "Una nota sobre los algoritmos lineales de tiempo esperado para encontrar cascos convexos", Computación , vol. 26, 1981, págs. 361-366.
- ^ Aloupis, Greg. "Una historia de algoritmos de casco convexo en tiempo lineal para polígonos simples" . Consultado el 11 de octubre de 2020 .
- ^ McCallum, Duncan; Avis, David (1979), "Un algoritmo lineal para encontrar el casco convexo de un polígono simple", Information Processing Letters , 9 (5): 201-206, doi : 10.1016 / 0020-0190 (79) 90069-3 , MR 0552534
- ^ Graham, Ronald L .; Yao, F. Frances (1983), "Encontrar el casco convexo de un polígono simple", Journal of Algorithms , 4 (4): 324–331, doi : 10.1016 / 0196-6774 (83) 90013-5 , MR 0729228
- ^ Lee, DT (1983), "Al encontrar el casco convexo de un polígono simple", International Journal of Computer and Information Sciences , 12 (2): 87–98, doi : 10.1007 / BF00993195 , MR 0724699
- ^ Consultelas notas de la conferencia de David Mount , incluida la lección 4, para conocer los desarrollos recientes, incluido el algoritmo de Chan .
- ^ Barber, C. Bradford; Dobkin, David P .; Huhdanpaa, Hannu (1 de diciembre de 1996). "El algoritmo de casco rápido para cascos convexos". Transacciones ACM en software matemático . 22 (4): 469–483. doi : 10.1145 / 235815.235821 .
- ^ Avis, David ; Bremner, David; Seidel, Raimund (1997), "¿Qué tan buenos son los algoritmos de casco convexo?", Geometría computacional: teoría y aplicaciones , 7 (5-6): 265-301, doi : 10.1016 / S0925-7721 (96) 00023-5.
Otras lecturas
- 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: Encontrar el casco convexo, págs. 947–957.
- Franco P. Preparata , SJ Hong . Cascos convexos de conjuntos finitos de puntos en dos y tres dimensiones , comun. ACM, vol. 20, no. 2, págs. 87-93, 1977.
- Mark de Berg ; Marc van Kreveld ; Mark Overmars y Otfried Schwarzkopf (2000). Geometría computacional (2ª ed. Revisada). Springer-Verlag . ISBN 978-3-540-65620-3.Sección 1.1: Un ejemplo: cascos convexos (describe los algoritmos clásicos para cascos convexos bidimensionales). Capítulo 11: Cascos convexos: págs. 235–250 (describe un algoritmo aleatorio para cascos convexos tridimensionales debido a Clarkson y Shor).
enlaces externos
- Weisstein, Eric W. "Casco convexo" . MathWorld .
- Casco convexo 2D, 3D y dD en CGAL , la biblioteca de algoritmos de geometría computacional
- Código Qhull para casco convexo, triangulación de Delaunay, diagrama de Voronoi e intersección de medio espacio
- Demostración como algoritmos Flash swf , Jarvis, Graham, Quick (divide y vencerás) y Chan
- Algoritmo de envoltura de regalos en C #