Quickhull
En geometría algorítmica , quickhull es un algoritmo para calcular el casco convexo . Es un algoritmo de divide y vencerás .
Principio
Tenga en cuenta en primer lugar que la envolvente convexa de un conjunto E de puntos se define por un subconjunto F de E . El principio del algoritmo es el siguiente. Primero, encontramos el punto P más a la izquierda y el punto Q más a la derecha (en caso de igualdad, elegimos arbitrariamente). Los puntos P y Q pertenecen a la envolvente convexa. Entonces podemos resolver el problema encontrando la envolvente convexa de los puntos sobre la línea (PQ) y la de los puntos debajo de la línea, luego concatenando las listas de puntos (sin repetir P y Q ). Los subproblemas tienen entonces una forma más restringida que la instancia original: tenemos dos puntos en una línea, de modo que todos los puntos están en el mismo lado de la línea, digamos a la izquierda de (PQ) , y todos los puntos que pertenecen a la línea están en el segmento [PQ] . Luego encontramos el punto H más alejado de la línea. La envolvente convexa de los puntos anteriores (PQ) se obtiene concatenando la envolvente convexa de los puntos a la izquierda de (PH) y la de los puntos a la izquierda de (HQ) . Podemos calcular estos conjuntos de forma recursiva (están en la misma configuración que antes).
- Los diferentes pasos del algoritmo Quickhull
Complejidad
El algoritmo tiene el mismo tipo de complejidad temporal que el algoritmo de clasificación quicksort , en el peor de los casos y en el promedio .
Historia
El algoritmo aparece en el libro Computational Geometry - An Introduction en 1985, donde los autores atribuyen las ideas a varios artículos de la década de 1970.
Notas y referencias
- “ Diseño de algoritmos y aplicaciones: Divide y vencerás para algorítmico Geometría ” , en Pierre-et-Marie-Curie Universidad ,2011
- Franco P. Preparata y Michael Ian Shamos, Geometría computacional - Introducción , Springer, 1985( ISBN 3-540-96131-3 , DOI 10.1007 / 978-1-4612-1098-6 )
- William F. Eddy, " Un nuevo algoritmo de casco convexo para conjuntos planos ", ACM Trans. Matemáticas. Softw. , vol. 3, n o 4, 1977, p. 398-403 ( DOI 10.1145 / 355759.355766 )
- Alex Bykat, " Casco convexo de un conjunto finito de puntos en dos dimensiones ", Inf. Proceso. Letón. , vol. 7, n o 6, 1978, p. 296-298 ( DOI 10.1016 / 0020-0190 (78) 90021-2 )
- PJ Green y BW Silverman, “ Construcción del casco convexo de un conjunto de puntos en el avión ” , Computación. J. , vol. 22, n o 3, 1979, p. 262-266 ( DOI 10.1093 / comjnl / 22.3.262 )
enlaces externos
- Jakob Westhoff, " Calcular un casco convexo - El algoritmo QuickHull " , una explicación detallada y un ejemplo de aplicación.
- Jeff Sember, “ Algoritmo QuickHull (video) ” Video de una ejecución paso a paso del algoritmo.