Divisão e Conquista: Par de Pontos mais Próximo
Fernando Lobo
Algoritmos e Estrutura de Dados II
1 / 18
Divisão e Conquista (cont.)
I
Problema: Dado um conjunto de pontos no plano, obter o par
de pontos mais próximo.
I
Input: P = {p1 , p2 , . . . , pn } com pi = (xi , yi ).
I
Output: Um par de pontos pi e pj cuja distância seja mı́nima.
2 / 18
I
É fácil fazer um algoritmo de complexidade Θ(n2 ), basta
calcular a distância entre cada par de pontos e escolher o par
com a distância mı́nima.
I
Vamos ver um algoritmo de complexidade Θ(n lg n) obtido
com a técnica de divisão e conquista.
3 / 18
Aplicações
I
Computação gráfica.
I
Sistemas de informação geográfica.
I
Controlo de tráfego aéreo.
I
etc.
4 / 18
Alguma ideia?
5 / 18
Divisão
I
Divide o conjunto P em dois conjuntos, Q e R, cada qual
com n/2 pontos.
I
A divisão é feita através de mediana da coordenada x.
6 / 18
Conquista
I
Resolve recursivamente o problema para Q e R.
I
Se o n.o de pontos for suficientemente pequeno (por exemplo
n <= 3) calcula-se à “força bruta”entre cada par de pontos.
7 / 18
Combinar: a parte difı́cil
I
Temos de o fazer em Θ(n) para obtermos uma complexidade
total de Θ(n lg n).
I
A distância mı́nima será o mı́nimo de três coisas: dQ , dR , dQR
(distância mı́nima entre um ponto de Q e um ponto de R).
8 / 18
Combinar (cont.)
I
Seja δ = min(dQ , dR )
I
Para sabermos se existe algum par de pontos pi e pj , tal que
pi ∈ Q, pj ∈ R e dist(pi , pj ) < δ, basta verificar os pontos
que estão a uma distância máxima de δ da linha L.
I
Chamemos a esse conjunto de pontos S.
I
Reparem que potencialmente, S poderá conter os n pontos
iniciais.
I
Ou seja, até aqui ainda não garantimos que não tenhamos de
calcular as distâncias entre cada ponto de Q com cada ponto
de R, o que daria Θ(n2 ).
9 / 18
10 / 18
I
Não pode haver mais do que um ponto por caixa. Se
houvesse, estariam do mesmo lado (ambos em Q ou ambos
em R) e teriam uma distância inferior a δ =⇒
uma contradição.
11 / 18
I
Se s1 e s2 são elementos de S e dist(s1 , s2 ) < δ, então s1 e s2
têm de estar no máximo a 11 posições um do outro na
sequência Sy (S ordenado por y ).
I
Porquê? Só pode haver um ponto por caixa.
I
Logo, 12 posições ou mais em y implica a existência de pelo
menos 2 linhas horizontais entre s1 e s2 =⇒ dist(s1 , s2 ) > δ.
12 / 18
I
Não é necessário estar a ordenar S em cada chamada
recursiva.
I
Se o fizéssemos obterı́amos a recorrência
T (n) = 2T (n/2) + Θ(n lg n).
I
Não dá para aplicar o Teorema Mestre. Mas pode-se provar
que T (n) = Θ(n lg n lg n).
I
O objectivo é obtermos a recorrência T (n) = 2T (n/2) + Θ(n).
I
Ou seja, o passo Combinar tem de ser feito em Θ(n).
13 / 18
I
A ideia é pré-ordenar o array P pela coordenada x (obtendo o
array Px ) e pela coordenada y (obtendo o array Py ).
I
Depois cada chamada recursiva recebe dois arrays de pontos
(ordenados por x e por y ).
Closest-Pair(P, n)
Px = P ordenado por x // Θ(n lg n)
Py = P ordenado por y // Θ(n lg n)
(p1, p2) = Closest-Pair-Rec(Px , Py , n)
14 / 18
Closest-Pair-Rec(Px , Py , n)
if n ≤ 3
Calcula a distância entre cada par de pontos e
retorna o par cuja distância é mı́nima.
else
// divide P em Q e R
Constrói Qx , Qy , Rx , Ry // Θ(n)
(q1, q2) = Closest-Pair-Rec(Qx , Qy , nQ)
(r 1, r 2) = Closest-Pair-Rec(Rx , Ry , nR)
dQ = dist(q1, q2)
dR = dist(r 1, r 2)
δ = min(dQ, dR)
x ∗ = coordenada x do último ponto do array Qx
// linha L : x == x ∗
// S = pontos em P que estão a uma distância
// máxima de δ de L.
Constrói Sy a partir de Py // Θ(n)
15 / 18
(continuação...)
Para cada s ∈ Sy , calcular a distância de s a cada um
dos próximos 11 pontos em Sy . Seja (s1, s2) o par
que obtém a distância mı́nima.
if dist(s1, s2) < δ
return (s1, s2)
elseif dQ < dR
return (q1, q2)
else return (r 1, r 2)
16 / 18
Para uma implementação concreta ainda faltam alguns
detalhes
I
Como obter Qx , Qy , Rx , Ry em Θ(n)?
I
A divisão do problema em dois subproblemas foi feita através
da mediana da coordenada x. Será que funciona se houver
pontos com a mesma coordenada x?
I
É trabalho para vocês pensarem.
17 / 18
Notas adicionais
I
Este algoritmo foi inventado em inı́cios dos anos 70 por
Shamos e Hoey.
I
O limite dos 11 pontos pode ser reduzido. O livro CLRS refere
apenas a verificação de 7 pontos.
I
Em 2011, José Luı́s Pereira (um colega vosso que estava a
fazer AED-II tal e qual como vós) demonstrou que com
algumas modificações ao algoritmo, basta apenas verificar 2
pontos. (os interessados podem ler
http://arxiv.org/abs/1010.5908)
18 / 18