Moyen le plus rapide pour trouver le minimum de la distance entre les points

J'ai un ensemble de points 2D et ont besoin de trouver le moyen le plus rapide de comprendre que la paire de points a la distance la plus courte dans l'ensemble.

Quel est le meilleur moyen pour ce faire? Mon approche est de les trier avec quicksort puis de calculer les distances. Ce serait en O(nlogn) + n) = O(nlogn).

Est-il possible de le faire dans le temps linéaire?

Grâce.

Comment arriver à faire le tri en deux dimensions des données avec quicksort? Et comment est-ce aider à trouver les deux points les plus proches?
Je viens de trier par abscisse. Fondamentalement, il semble que j'ai implémenté l'algorithme expliqué dans en.wikipedia.org/wiki/Closest_pair_problem. Tout d'abord trier par x, puis à diviser et conquérir. Il semble donc il n'y a pas de moyen plus rapide.
Tri par X n'est d'aucune valeur réelle à tous, depuis les points les plus proches peuvent ne pas avoir fermer X les valeurs. Et le tri par X ne réduit pas le besoin de comparer tous les points à l'encontre de tous les autres de trouver le point le plus proche de la paire.
En fait, il ne. Regardez le lien Wikipedia ci-dessus et de le diviser et conquérir solution. Il est O(N log N).
L'article de Wikipédia dit que c'est en fait O(n log log n) si le sol est une constante de temps de fonctionnement (cependant, je ne pense pas que c'est en fait, pour arbitrairement grands nombres)

OriginalL'auteur | 2009-04-25