Quickhull
From Wikipedia, the free encyclopedia
Tipo
Algoritmo Geométrico
Problema que resuelve
Cierre convexo
Creador
Barber, Dobkin y Huhdanpaa[1]
Fecha
1996
| Quickhull | ||
|---|---|---|
 Ejecución paso a paso del algoritmo Quickhull | ||
| Tipo | Algoritmo Geométrico | |
| Problema que resuelve | Cierre convexo | |
| Creador | Barber, Dobkin y Huhdanpaa[1] | |
| Fecha | 1996 | |
| Clase de complejidad | P | |
| Tiempo de ejecución | ||
| Peor caso | ||
| Caso promedio | ||
Quickhull es un método para calcular el cierre convexo de un conjunto finito de puntos (generalmente en el plano 2D, pero también existen versiones para dimensiones superiores). Emplea una técnica basada en divide y vencerás similar a la empleada por el algoritmo de ordenación quicksort, del que toma su nombre.[1]
Su complejidad promedio es Θ(n * log(n)), aunque en el peor caso puede tomar O(n2) en situaciones de alta simetría o con conjuntos de puntos situados en forma de circunferencia.
