ALGORITMO DE ANDREW


NOTAS PREVIAS


Es una variación del Scan de Graham, donde cambia la forma de preordenar los puntos.


DESCRIPCIÓN DEL ALGORITMO


  1. Determinar los puntos de mayor y menos abcisa en la nube de puntos y trazar una recta que pase por ellos.

  2. Con los puntos que quedan por encima de la recta

    1. Ordenarlos de mayor a menor

    2. Aplicar el Scan de Graham a dichos puntos

    3. Se obtiene una linea poligonal (cierre superior)

  3. Con los puntos que quedan por debajo de la recta

    1. Ordenarlos de menor a mayor

    2. Aplicar el Scan de Graham a dichos puntos

    3. Se obtiene una linea poligonal (cierre inferior)

  4. Concatenar el cierre superior y el cierre inferior


COMPLEJIDAD DEL ALGORITMO


  • Ordenar los puntos: O(N.LogN)
  • Repartir los puntos encima y debajo de la recta: O(N)
  • Aplicar Scan a ambos conjuntos de puntos: O(N)
  • Concatenar los cierres: O(N)
O(N.LogN)