ALGORITMO DE GRAHAM
(SCAN DE GRAHAM)


NOTAS PREVIAS


Este algoritmo surgió a finales de los 60, cuando en los laboratorios Bell se necesitaba calcular el cierre convexo de unos 10.000 puntos, y con uno de los algoritmos de por entonces, de O(N^2) resultaba demasiado lento. Entonces Graham lo solucionó con el presente algoritmo.


DESCRIPCIÓN DEL ALGORITMO


  1. Hallar un punto q interior al cierre convexo

  2. Ordenar los N puntos angularmente en sentido positivo alrededor de él.
    Llamaremos p(n) al punto situado en la posición n

  3. (Scan) Recorrer la lista ordenada de puntos hasta que se llegue al punto de partida

    Examinar tripletas de puntos consecutivos [p(i-1),p(i),p(i+1)]

    1. Si la tripleta es un giro a la izquierda se avanza un vértice y se comprueba [p(i),p(i+1),p(i+2)]

    2. Si la tripleta no es un giro a la izquierda, entonces p(i) no es un vértice, ya que es interior a [q,p(i-1),p(i+1)].

      1. Eliminar p(i)

      2. Comprobar la Tripleta [p(i-2),p(i-1),p(i+1)]

  4. Los puntos que queden son los vértices de la envolvente convexa.


COMPLEJIDAD DEL ALGORITMO


  • Encontrar punto Interior: O(N)
  • Ordenar los puntos alrededor del interior: O(N.logN)
  • Encontrar el vértice donde iniciar el scan de Graham: O(N)
  • Scan de Graham: O(N)
O(N.LogN)