Diferencia entre revisiones de «Envolvente convexa»
Contenido eliminado Contenido añadido
mSin resumen de edición |
mSin resumen de edición |
||
Línea 25:
* '''Jarvis march''' o ''gift wrapping algorithm''. Propuesto por R. A. Jarvis en 1973. Es uno de los más simples y posee una [[complejidad computacional]] O(''nh''). En el peor de los casos su complejidad será O(''n<sup>2</sup>'').
* '''[[Método de Graham|Graham scan]]'''. Publicado en 1972, es mucho más eficiente y posee una complejidad computacional O(''n'' log ''n''). Si los puntos se encuentran ordenados por una de las coordenadas o por el ángulo a un vector fijo entonces la complejidad es O(''n'').
* '''Divide y vencerás''' (''Divide and conquer''). Otro algoritmo de complejidad O(''n'' log ''n'') publicado en 1977 por Franco P. Preparata y Hong. También es aplicable al caso tridimensional.<ref name=Preparata>{{Cita publicación|apellidos=Preparata |nombre=Franco P.|author-link=Franco P. Preparata|apellidos2=Hong|nombre2=S.J. |título=Convex hulls of finite sets of points in two and
three dimensions |publicación=[[Communications of the ACM]] |volumen=20 |número=2 |año=1977 |doi=10.1145/359423.359430 |issn= |url= }}</ref>
| |||