J'ai un ensemble de points 2D et j'ai besoin de trouver le moyen le plus rapide pour déterminer quelle paire de points a la plus courte distance dans l'ensemble.Le moyen le plus rapide pour trouver la distance minimale entre les points
Quelle est la meilleure façon de procéder? Mon approche est de les trier avec quicksort puis de calculer les distances. Ce serait O (nlogn + n) = O (nlogn).
Est-il possible de le faire en temps linéaire?
Merci.
No. distance minimum entre tous les points O (n^2) parce que vous devez comparer tous les points contre tous les autres points. Techniquement, c'est n * n/2 parce que vous n'avez qu'à remplir remplir la moitié de la matrice.
Il existe des algorithmes plus rapides pour trouver le plus proche voisin à un point donné. Malheureusement, vous devez ensuite faire cela pour chaque point pour trouver les deux points les plus proches.
Le diagramme n'est pas un algorithme. L'algorithme Fortune produit le diagramme. http://en.wikipedia.org/wiki/Fortune%27s_algorithm. Je ne suis pas sûr que cela s'applique, car il partitionne l'espace plutôt que de comparer des points. –
La plus proche paire de problème points ou le plus proche problème de paire est un problème de computational geometry: donné n points dans l'espace métrique, trouver une paire de points avec la plus petite distance entre eux ...
Dans le modèle de calcul qui suppose que le floor function est calculable en temps constant le problème peut être résolu en O (n log log n). Si nous permettons randomisation à utiliser en même temps que la fonction du sol, le problème peut être résolu en O (n) temps ..
Si vous pouviez sonder une quantité constante de chaque point et utiliser l'approfondissement itérative DFS , vous ne vérifiez jamais plus loin que les deux points les plus proches ... et puisque vous n'êtes pas dépendant d'un échec, vous n'aurez jamais besoin de recalculer la façon dont l'ID DFS a tendance à se comporter.
Comment trier les données bidimensionnelles avec le tri rapide? Et comment cela aide-t-il à trouver les deux points les plus proches? –
Je viens de les trier par coordonnées x. Fondamentalement, il semble que j'ai mis en œuvre l'algorithme expliqué à http://en.wikipedia.org/wiki/Closest_pair_problem. Commencez par trier par x, puis divisez et conquérez. Donc, il semble qu'il n'y a pas de moyen plus rapide. –
Le tri par X n'a aucune valeur réelle, car les points les plus proches peuvent ne pas avoir de valeurs X proches. Et le tri par X ne réduit pas le besoin de comparer chaque point contre tous les autres points pour trouver la paire la plus proche. –