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