APROXIMACIÓN SUPERIOR


NOTAS PREVIAS


Este algoritmo da un método aproximado para calcular el cierre convexo de una nube de puntos. Se llama Aproximación superior porque el cierre que nos dará contiene al cierre exacto.


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, escoger los puntos de mayor y menor ordenada y proyectarlos sobre las líneas verticales que delimitan dicha franja. El par de proyecciones que se genera en cada caso serán los nuevos puntos a considerar (Hay como mucho 4K+4 puntos).
  4. Aplicar un algoritmo conocido para calcular el cierre convexo de los puntos obtenidos. Se recomienda usar Andrew por estar los puntos ordenados.
Nota: Se puede demostrar que la distancia máxima entre un punto del cierre aproximado y otro del cierre real 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)
  • Obtener los puntos mediante las proyecciones: O(K)
  • Aplicar Andrew: O(K)
O(N+K)