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)
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
Vous devez vous connecter pour publier un commentaire.
Il est en fait:
OriginalL'auteur leiz
Si vous pouviez sonde une quantité constante à partir de chaque point et d'utiliser l'approfondissement itératif DFS, youd jamais vérifier encore plus en dehors que sur les deux points les plus proches...et puisque vous n'êtes pas dépendant d'un échec de passe, vous n'auriez jamais besoin de recalculer le moyen ID DFS tend à.
OriginalL'auteur max
Pas. La distance minimale entre TOUS les points de O( n ^ 2 ) parce que vous devez comparer tous les points à l'encontre de tous les autres points. Techniquement, c'est n * n /2 parce que vous avez seulement à remplir à remplir la moitié de la matrice.
Il existe des algorithmes plus rapides sont pour trouver le plus proche voisin d'un point donné. Malheureusement, vous devez alors le faire pour chaque point de trouver la plus proche de deux points.
OriginalL'auteur S.Lott