PDF de programación - Análisis y Diseño de Algoritmos - Puntos más cercanos

Puntos más cercanos
Puntos más cercanos
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos

Puntos más cercanos
Puntos más cercanos

Problema
Problema::

puntos en el

Dados n
Dados n puntos
puntos
puntos con la
[[CasoCaso particular del “

con la menormenor distancia
particular del “vecino

encontrar la la pareja

plano, , encontrar
distancia euclídea
vecino másmás cercano

pareja de de
entre ellosellos..
cercano” y de MST]
” y de MST]

euclídea entre

en el plano

Aplicaciones::
Aplicaciones
Informática
Informática gráfica
de de información

gráfica, , visión
información geográfica

geográfica (GIS)…
(GIS)…

visión porpor computador

computador, , sistemas
sistemas

Algoritmo porpor fuerza
Algoritmo
Comprobar
Comprobar todos
 Versión

Versión 11--D: O(n log n).
D: O(n log n).

fuerza bruta
todos los pares de

bruta: :
los pares de puntos

puntos p y q:

p y q: ΘΘ(n(n22).).

11

Puntos más cercanos
Puntos más cercanos

Algoritmo
Algoritmo divide y
Primer
Primer intento

intento: : División

divide y vencerás
vencerás::

División en 4

en 4 cuadrantes

cuadrantes……

L
L

Puntos más cercanos
Puntos más cercanos

divide y vencerás
vencerás::

Algoritmo
Algoritmo divide y
Primer
Primer intento
¡¡Resulta
Resulta imposible

intento: : División

imposible asegurar

División en 4

en 4 cuadrantes
asegurar n/4 n/4 puntos

cuadrantes……

puntos porpor cuadrante
cuadrante!!

L
L

22

33

Puntos más cercanos
Puntos más cercanos

divide y vencerás
vencerás::

Algoritmo
Algoritmo divide y
Segundo
Segundo intento
Línea
Línea vertical con n/2

intento: :

vertical con n/2 puntos

puntos a a cada

cada ladolado……

L
L

Puntos más cercanos
Puntos más cercanos

divide y vencerás
vencerás::

Algoritmo
Algoritmo divide y
División
División: :
Encontrar
Encontrar la la pareja

pareja másmás cercana

cercana en en cada

cada mitadmitad……

L
L

44

55

Puntos más cercanos
Puntos más cercanos

Algoritmo
Algoritmo divide y

divide y vencerás
vencerás::

Combinación: : Encontrar
Combinación
punto
punto a a cada
cada ladolado de la

de la línea

línea……

Encontrar la la pareja

pareja másmás cercana

cercana con un
con un

L
L

66

Puntos más cercanos
Puntos más cercanos

Algoritmo
Algoritmo divide y

divide y vencerás
vencerás::

Observación
Observación: : SóloSólo nosnos interesan
punto
punto a a cada

cada ladolado de la

de la línea

interesan laslas parejas

parejas con un
con un

línea sisi están

están a a menosmenos de de δδδδδδδδ de LL

L
L

D

I

δ = min(I,D)

77

Puntos más cercanos
Puntos más cercanos

Algoritmo
Algoritmo divide y

divide y vencerás
vencerás::

Observación
Observación: : SóloSólo nosnos interesan
punto
punto a a cada

cada ladolado de la

de la línea

interesan laslas parejas

parejas con un
con un

línea sisi están

están a a menosmenos de de δδδδδδδδ de LL

L
L

D

δ

I

δ = min(I,D)

Puntos más cercanos
Puntos más cercanos

Algoritmo
Algoritmo divide y
Solución
Solución eficiente
22δδδδδδδδ en función de su coordenada y...

vencerás::
divide y vencerás
eficiente: : Ordenar
Ordenar los

los elementos

elementos de la

de la franja
franja

L
L

5

2

7

6

4

3

1

D

δ

I

δ = min(I,D)

88

99

Puntos más cercanos
Puntos más cercanos

Algoritmo
Algoritmo divide y
… y … y sólosólo comprobar
posiciones en la lista ordenada en función de y.
posiciones

divide y vencerás
vencerás::
comprobar aquéllos

aquéllos queque están

están a a menosmenos de 12
de 12

L
L

5

2

7

6

4

3

1

D

δ

I

δ = min(I,D)

1010

Puntos más cercanos
Puntos más cercanos

Propiedad

Si s y s’ son puntos de la franja
2δ tales que d(s,s’)< δ, para
encontrarlos no tendremos que
calcular más de 11 distancias
por punto si los ordenamos
por punto si los ordenamos
por su coordenada y.

2 filas

i

27

Demostración:
 No hay dos puntos en la

misma región de tamaño ½δ x ½δ.
 Dos puntos separados por dos filas

están a una distancia ≥ 2(½δ).

39

j

½δ
½δ

½δ

½δ

30

28

25

δ

31

29

26

δ

Algoritmo
Algoritmo

Closest-Pair (p1, …, pn)
{

Compute separation line L such that half the points
are on one side and half on the other side.

δδδδ1 = Closest-Pair(left half)
δδδδ2 = Closest-Pair(right half)
δδδδ = min(δδδδ1, δδδδ2)
δδδδ = min(δδδδ1, δδδδ2)

O(n log n)

2T(n / 2)

Delete all points further than δδδδ from separation line L

O(n)

Sort remaining points by y-coordinate.

Scan points in y-order and compare distance between
each point and next 11 neighbors. If any of these
distances is less than δδδδ, update δδδδ.

return δδδδ.

}

O(n log n)

O(n)

1212

Eficiencia
Eficiencia

T(n) ≤ 2T n /2(

) + O(n log n) ⇒ T(n) = O(n log2 n)

NNOTAOTA

Se Se puede
puede mejorar
puede mejorar
Se Se puede
reordenan desde
reordenan

mejorar la la eficiencia
mejorar la la eficiencia
desde cero los

eficiencia del del algoritmo
algoritmo sisi no se
algoritmo sisi no se
eficiencia del del algoritmo
no se
no se
de la franja

cero los puntos

puntos de la

franja 2δ..

Haciendo queque cada
ordenados tanto

¿¿Cómo
Cómo? ? Haciendo
puntos
puntos ordenados
coordenada
coordenada x [y

x [y mezclando

cada llamada

llamada recursiva

recursiva devuelva

devuelva los
los

tanto porpor la la coordenada

coordenada y y como
listas ordenadas

como porpor la la
ordenadas en O(n)].
en O(n)].

mezclando laslas listas

T(n) ≤ 2T n /2(


) + O(n) ⇒ T(n) = O(n log n)

1313