Par de pontos mais próximo
Origem: Wikipédia, a enciclopédia livre.
Par de pontos mais próximo
- Dado um conjunto de N pontos em um plano, encontrar os dois pontos do conjunto que guardam a menor distância um do outro.
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. Os pesquisadores em geometria computacional encontraram uma série de algoritmos capazes de resolver o problema com complexidade de tempo O(N log N).
Para sistemas modernos que precisam lidar com grandes quantidades de dados relacionados com objetos geométricos a diferença entre N2 e N log N representa a diferença entre segundos e dias de processamento para a resolução de um problema. Esse aspecto realça a busca pelo ótimo em complexidade computacional por parte da geometria computacional.
