APROXIMACIÓN INFERIOR


NOTAS PREVIAS


Este algoritmo da un método aproximado para calcular el cierre convexo de una nube de puntos. Se llama Aproximación inferior porque el cierre que nos dará es un subconjunto del cierre exacto, es decir, habrá puntos que caigan fuera del cierre aproximado.


DESCRIPCIÓN DEL ALGORITMO


  1. Encontrar los puntos Xmin y Xmax con mayor y menor abcisa.
  2. Dividir el espacio que hay entre Xmin y Xmax en K franjas verticales de igual anchura.
  3. Para cada franja, incluyendo las franjas de los extremos escoger los puntos de mayor y menor ordenada (Hay K+2 franjas y 2k+4 puntos).
  4. Aplicar un algoritmo conocido para calcular el cierre convexo de los puntos obtenidos. Se recomienda usar Andrew, ya que los puntos están casi ordenados por la abcisa, faltaría ordenar los dos puntos de cada franja.
Nota: Se puede demostrar que la distancia máxima entre un punto fuera del cierre aproximado y dicho cierre es (Xmax-Xmin)/K. Luego a mayor valor de K mejor será la aproximación.


  


COMPLEJIDAD DEL ALGORITMO


  • Búsqueda de Xmin y Xmax: O(N)
  • Dividir el espacio en franjas y
    asignar los 2 puntos a cada una: O(N)
  • Ordenar la muestra: O(K)
  • Aplicar Andrew: O(K)
O(N+K)