Problema de Encontrar o Par Mais Próximo

 - Entrada: um conjunto P = {p1, p2, ..., pn} de n pontos no plano R^2
 
 - Distância Euclidiana: 
 
    - Dados pontos pi = (xi, yi) e pj = (xj, yj)
	
	- d(pi, pj) = ((xi - xj)^2 + (yi - yj)^2)^1/2

 - Solução: um par p, q em P que minimiza a distância d(p, q) sobre todos os pares de pontos em P
 
 
 
Algoritmo por busca exaustiva (composto de dois laços aninhados) compara a distância entre todos os (n escolhe 2) = n(n-1)/2 pares de pontos e devolve o par com a menor distância em tempo O(n^2)



Vamos tentar fazer melhor usando o método de divisão e conquista

Para colocar alguma estrutura na instância

 - criamos duas cópias de P chamadas Px e Py
 
   - Sendo que Px é ordenada pelas coordenadas x dos pontos
   
   - E Py é ordenada pelas coordenadas y dos pontos
   
   - Note que esse procedimento leva tempo O(n log n)
 
 - Pra intuir porque ordenar os pontos é uma boa ideia
 
    - Observem que a versão deste problema na linha (dimensão R) 
	
	   - ainda tem (n escolhe 2) pares para comparar
	   
	   - mas pode ser resolvida em tempo linear uma vez que os pares estejam ordenados (por que?)



(p, q) ParMaisProximo(Px, Py) {

	Se o número de pontos for menor que 4 (caso base)
		encontre o par mais próximo diretamente e devolva-o
	
	Divida Px em Lx e Rx (e Py em Ly e Ry) de modo que
		a metade dos pontos mais a esquerda fique nos componentes L
		a metade mais a direita fique nos compontentes R
		e os subconjuntos continuem ordenados
		(isso deve ser feito em tempo linear. Como?)
	
	(pl, ql) ParMaisProximo(Lx, Ly)
	(pr, qr) ParMaisProximo(Rx, Ry)
	
	(pd, qd) ParMaisProximoDividido(Px, Py)
	
	Devolva o melhor entre (pl, ql), (pr, qr), (pd, qd)
	(melhor é o par com menor distância)
	
}


Um detalhe crucial é que só precisamos nos preocupar em saber o par dividido mais próximo caso ele seja menor que o par mais próximo não dividido. Essa ideia nos permite fortalecer o algoritmo da seguinte forma.



(p, q) ParMaisProximo(Px, Py) {

	Se o número de pontos for menor que 4 (caso base)
		encontre o par mais próximo diretamente e devolva-o
	
	Divida Px em Lx e Rx (e Py em Ly e Ry) de modo que
		a metade dos pontos mais a esquerda fique nos componentes L
		a metade mais a direita fique nos compontentes R
		e os subconjuntos continuem ordenados
		(isso deve ser feito em tempo linear. Como?)
	
	(pl, ql) ParMaisProximo(Lx, Ly)
	(pr, qr) ParMaisProximo(Rx, Ry)
	
	delta = min{d(pl, ql), d(pr, qr)}
	
	(pd, qd) ParMaisProximoDividido(Px, Py, delta)
	
	Devolva o melhor entre (pl, ql), (pr, qr), (pd, qd)
	(melhor é o par com menor distância)
}


Agora o ParMaisProximoDividido poderá usar a informação delta para melhorar sua busca

(p, q) ParMaisProximoDividido(Px, Py, delta) {

	seja x' a coordenada x em torno da qual os pontos foram divididos entre esquerda e direita
	
	seja Sy a restrição do vetor ordenado Py sobre os pontos com coordenada x entre x' - delta e x' + delta
	(conseguimos fazer isso em tempo linear? porque podemos fazer isso sem comprometer a solução?)
	
	dmin = delta
	p = q = null
	
	for (i = 1; i < |Sy|; i++)
		for (k = 1; k <= min{7, |Sy| - 1}; k++)
			if (d(Sy[i], Sy[i+k]) < dmin)
				p = Sy[i]
				q = Sy[i+k]
				dmin = d(p, q)
	
	return (p, q)
}

Qual a eficiência do algoritmo ParMaisProximoDividido? O(n), pois o laço interno executa um número constante (<= 7) vezes

O que isso implica para a eficiência do algoritmo ParMaisProximo? O(n log n), pois este fica com uma recorrência T(n) = 2 T(n/2) + cn

Por que o algoritmo ParMaisProximoDividido está correto?

 - Vamos ver uma demonstração em duas partes
 
 
 
 - Primeiro, vamos verificar que se dois pontos estão mais próximos que a distância delta, então a diferença entre suas coordenadas x (e entre suas coordenadas y) deve ser menor que delta
 
    - sendo p = (xp, yp) e y = (xq, yq)
	
	- d(p, q) = ((xp - xq)^2 + (yp - yq)^2)^1/2
			  >= (xp - xq)^2^1/2
			  = |xp - xq|
			  (vale o mesmo para a coordenada y)

 - Portanto, se um par dividido tiver distância menor que delta, é necessário que suas coordenadas x estejam entre x' - delta e x' + delta
 
 - Além disso, considere um suposto par mais próximo dividido (p, q)
 
    - A diferença entre suas coordenadas y também tem que ser menor que delta
	
	- Assim, p e q devem estar numa região com
	
	   - dois deltas de largura (cujo centro é x')
	   
	   - um delta de altura (cuja base é o valor da menor coordenada y entre p e q)



 - Segundo, vamos observar que em qualquer dos lados dessa região dois pontos não podem estar a uma distância menor que delta
 
    - Caso contrário, esses pontos implicariam um delta menor que o encontrado (contradição)



 - Para fechar a prova, divida a região em quadrados de lado delta/2
 
 - Observe que dois pontos não podem estar no mesmo quadrado, pois
 
    - Eles estariam do mesmo lado e teriam distância <= (delta/2)*2^1/2 < delta

 - Observe também que a região tem exatamente 8 desses quadrados
 
 - Como em cada um pode haver no máximo um ponto, temos no máximo 8 pontos entre p e q inclusive
 
 - Portanto, quando o algoritmo examina os próximos 7 pontos a partir do ponto corrente, se houver um par mais próximo dividido envolvendo o ponto corrente, este par será encontrado.