Diferencia entre revisiones de «Envolvente convexa»
Contenido eliminado Contenido añadido
m Bot: ortografía y otros (v0.32); cambios triviales |
|||
Línea 20:
*'''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 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.
| |||