Divide & Conquer: problema del par más
cercano
Geometría Computacional.
Lic. Yessika Labrador
Contenido Introducción. El Problema. Solución por Fuerza Bruta. Solución Divide & Conquer. Conclusión
Introducción La geometría computacional se encarga del diseño y
análisis de algoritmos para resolver problemas geométricos.
Son útiles en campos como la graficación por computadora, estadística, procesamiento de imágenes, etc.
El problema del par más cercano Dado un conjunto Q de n puntos en el plano, con n≥2,
determinar un par de puntos más cercanos.
La unidad de medida de distancia es la distancia euclidiana:
Algoritmo de fuerza brutaParMásCercanoFB
minDist ∞para cada p in P:
para cada q in P: si p ≠ q y dist(p,q) < minDist:
minDist dist(p,q) parCercano (p,q)
retornar parCercano
Tiempo del algoritmo: O(n2)
Algoritmo Divide & Conquer. Toma como entrada las matrices X e Y, X,Y Q. X está ordenada monótonamente creciente por la
coordenada x. Y está ordenada por la coordenada y. Si |P|≤3 se realiza la invocación del método de fuerza. Si |P|>3 la invocación recursiva se lleva a cabo.
Algoritmo Divide & Conquer. Divide:
Se encuentra una línea vertical l que divide a P en dos: PL y PR, |PL| = (|P|/2) , |PR| = (|P|/2)
X se divide en XL y XR. Y se divide en YL y YR.
Algoritmo Divide & Conquer. Conquer:
Se hacen dos llamadas recursivas: para encontrar el par más cercano de puntos en el PL y para encontrar el par más cercano de puntos en PR.
Dado δL y δR δ = min(δL, δR).
Algoritmo Divide & Conquer. Composición de soluciones:
El par más cercano es el par con la distancia δ encontrada por las llamadas recursivas.
Es un par de puntos con un punto en el PL y el otro en PR.
Algoritmo Divide & Conquer. Los puntos deben estar en la franja vertical de
ancho 2δ con centro en l. Se crea Y', con los puntos de Y que están en la
franja. Para cada punto p en Y', buscamos la distancia
entre p y los próximos 7 puntos en Y'. Si δ'<δ retorna δ', en caso contrario retorna δ.
Algoritmo Divide & Conquer.Correctitud del Algoritmo: |P|≤3 nos aseguramos de que no tratamos de resolver
un subproblema consiste en un solo punto.
Sólo tenemos que comprobar los 7 puntos posteriores a cada punto P de Y'.
Algoritmo Divide & Conquer.parMásCercano (XP, YP)
Si N ≤ 3 entonces retornar par más cercano con algoritmo de fuerza brutaSino xL puntos de XP hasta (N/2) xR puntos de XP desde (N/2) xm xP(techo(N/2))
yL { p ∈ yP : px ≤ xm } yR { p ∈ yP : px > xm }
(dmin, parMin) menorPar(parMásCercano (xL, yL), parMásCercano (xR, yR))
Y’ { p YP : |xm - px| < dmin }
para cada p Y’ para los 7 sucesores de p Y’ si |p - q| < dmin entonces
(dmin, parMin) (|p - q|, {p, q})
retornar (dmin, parMin)
Algoritmo Divide & Conquer.
Tiempo de Ejecución Preordenar el arreglo O(n logn)
T(n), tiempo de ejecución de cada etapa recursiva. T'(n), tiempo de ejecución del algoritmo total.
T'(n) = T(n) + O(n lgn)
T(n) = 2T(n/2)+O(n) si n>3 O(1) si n≤3
Entonces, T(n)=O(n lgn) y T'(n)=O(n lgn).
Conclusión El algoritmo Divide & Conquer O(n lgn) es mucho más
eficiente que un algoritmo de fuerza bruta O(n2).
Al considerar las posibles posiciones de los puntos en el rectángulo, Lerner y Johnsonbaugh demostraron que basta comparar cada punto de la franja con los siguientes tres puntos.
Existen otros enfoques (triangulación de Delaunay, diagrama de Voronoi) que toman O(n lgn) para el problema en el plano. Sin embargo no son eficaces para dimensiones >2. El algoritmo Divide&Conquer puede ser generalizado para tomar O(n lgn).
Divide & Conquer: problema del par más
cercano