Problema do par de pontos mais próximo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ilustração do par de pontos mais próximo.

O problema do par de pontos mais próximo consiste em, dado um conjunto de n pontos num espaço métrico, encontrar os dois pontos do conjunto que possuem a menor distância um do outro. A versão em duas dimensões, para pontos num plano,[1] estava entre os primeiros problemas geométricos que foram tratados na origem do estudo de complexidade computacional de algoritmos geométricos.

Se forem computadas as distâncias entre todos os pares de pontos do conjunto, há n(n-1)/2 computações antes de ser possível decidir inequivocamente qual o par que apresenta a menor distância. Esse algoritmo é conhecido como força bruta e tem complexidade de tempo O(n2), ou seja, seu tempo de execução é proporcional ao quadrado do número de pontos do conjunto considerado. Porém, pesquisadores em geometria computacional descobriram que este problema pode ser resolvido em tempo O(n log n) em um espaço euclidiano ou espaço Lp de dimensão d fixa.

No modelo computacional que assume que a função chão é computada em tempo constante, o problema pode ser resolvido em tempo de O(n log log n).[2] Se for permitido o uso de escolhas aleatórias em conjunto com a função chão, o problema pode ser resolvido em tempo O(n).[3] [4]

Problema no plano[editar | editar código-fonte]

O problema no plano pode ser resolvido em tempo de O(n log n) usando divisão e conquista, nos seguintes passos[1] :

  1. Ordenar os pontos de acordo com as coordenadas x;
  2. Dividir o grupo de pontos em dois subgrupos de mesmo tamanho por uma linha vertical x=x_{mid}
  3. Resolver o problema recursivamente para os dois grupos, resultando nas distâncias mínimas nos lados esquerdos e direitos, d_{Emin} e d_{Dmin} respectivamente.
  4. Encontrar a distância mínima d_{EDmin} entre um par de pontos onde cada ponto está em um lado diferente da linha vertical.
  5. A resposta final é o mínimo entre d_{Emin}, d_{Dmin}, and d_{EDmin}.

Por sua vez, o quarto passo pode ser realizado em tempo linear, pois já sabemos que o par de pontos mais próximos não podem ter distância maior que dist=\min(d_{Emin}, d_{Dmin}). Portanto para cada ponto p do lado esquerdo da linha vertical é feita feita a comparação das distâncias para pontos que estão do lado direito e dentro de um retângulo de dimensões (dist, 2 * dist), ou seja, pontos que possuem coordenada x com uma distância máxima dist para a direita de p e coordenada y com distância máxima dist para cima ou para baixo de p.

Considerando que o par de pontos mais próximos definem uma aresta na triangulação de Delaunay, e corresponde a duas faces adjacentes no diagrama de Voronoi, o par de pontos mais próximos pode ser determinado em tempo linear quando é dado junto ao problema uma dessas duas estruturas. Computar a triangulação de Delaunay, assim como o diagrama de Voronoi, leva tempo O(n log n). Porém para uma dimensão d maior que 2, esse tempo irá aumentar, enquanto que o algoritmo com divisão e conquista pode ser generalizado mantendo tempo O(n log n) para qualquer d.

Referências[editar | editar código-fonte]

  1. a b M. I. Shamos e D. Hoey. "Closest-point problems." Em Proc. 16th Annual IEEE Symposium on Foundations of Computer Science (FOCS), p. 151—162, 1975
  2. S. Fortune e J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), p. 20—23, 1979
  3. S. Khuller e Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995
  4. Richard Lipton (24 September 2011). Rabin Flips a Coin.