ALGORITMO DE JARVIS
(ENVOLTURA DEL REGALO)


NOTAS PREVIAS


La idea intuitiva del algoritmo consiste en imaginar una recta que se desplaza desde menos infinito hacia arriba hasta tocar un punto del conjunto de puntos. Luego, dicha recta va rodeando la nube de puntos en sentido positivo, girando en cada vértice hasta tocar el siguiente, de modo que al final la envuelve por completo.


DESCRIPCIÓN DEL ALGORITMO


  1. Dado el conjunto de puntos S, tomamos el punto P que tenga menor ordenada y mayor abcisa. y trazamos una recta r que pase por P y sea paralela al eje de abcisas.

  2. Para cada punto de S trazar lineas que los unan con P. El próximo vértice del cierre convexo será el punto Q que forme el mínimo ángulo respecto a la recta r anterior.

  3. Si Q no es el punto de partida, Repetir 2 tomando P=Q y r como la recta formada por P y Q.


COMPLEJIDAD DEL ALGORITMO


  • Encontrar el punto de menor ordenada: O(N)
  • Encontrar el menor ángulo: O(N^2)
O(N^2)