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 bruta
ParMá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 bruta
Sino
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)
O(1)
si n>3
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
Descargar

Divide & Conquer: problema del par más cercano