Algorithme pour trouver les points qui sont les plus éloignées — mieux que O(n^2)?
Dans mon programme, j'ai un ensemble de points. Pour des fins de mise à l'échelle, je suis à la recherche pour les deux nœuds qui sont les plus éloignées, et ensuite calculer un facteur de multiplier toutes les coordonnées de sorte que la distance maximale est égale à une certaine prédéfini j'définir.
L'algorithme que je suis aide à trouver les deux points les plus éloignées est toutefois problématique pour les grands ensembles de points, comme il est O(n^2); pseudo-code (les distances qui ont déjà été calculées sont ignorés):
for each point in points:
for each other point in points:
if distance between point and other point > max
max = distance between point and other point
Est-il quelque chose de plus rapide?
double possible de algorithme Efficace pour trouver les sphères les plus éloignées dans la grande collection
J'ai posté un algorithme O(n) qui comprend une marge d'erreur qui peut être utile à votre problème particulier de la mise à l'échelle.
je pense que cela va sauter répété index et déjà visité (mais dans l'ordre inverse) paires d'indices: for (int i = 0, j; i < count - 1); i++) for (j = i + 1; j < nombre ; j++) //pour la première boucle for, vous pouvez utiliser (count - 1) ou de compter parce que la boucle interne ne s'exécutera pas à ce point quand même.
J'ai posté un algorithme O(n) qui comprend une marge d'erreur qui peut être utile à votre problème particulier de la mise à l'échelle.
je pense que cela va sauter répété index et déjà visité (mais dans l'ordre inverse) paires d'indices: for (int i = 0, j; i < count - 1); i++) for (j = i + 1; j < nombre ; j++) //pour la première boucle for, vous pouvez utiliser (count - 1) ou de compter parce que la boucle interne ne s'exécutera pas à ce point quand même.
OriginalL'auteur houbysoft | 2011-06-29
Vous devez vous connecter pour publier un commentaire.
Si vous avez juste besoin de la dimension et de ne pas les points précis que vous pouvez le faire en O(n) le temps avec une certaine marge d'erreur. Penser le simple cas de la fabrication d'une boîte englobante. Calculer le minimum de la valeur de x à partir de tous les points, le maximum de x, le y minimale et la maximale y. Ces quatre numéros de vous donner un maximum de délimitation de zone autour de vos points avec max d'erreur de 1 - (1/sqrt(2)) d'environ 30%. Vous pouvez réduire ce en ajoutant plus de côtés à votre place. Réfléchir sur le cas d'un octogone. Pour calculer les valeurs min et max pour les autres côtés, vous devez faire pivoter votre système de coordonnées.
Erreur vs moment de l'exécution se décompose comme ceci.
forme - run time - max d'erreur
Voici l'équation pour le max d'erreur, je suis venu avec.
Laissez-moi savoir si je dois ajouter un diagramme expliquant cela.
OriginalL'auteur gradbot
Suivantes peuvent aider à mettre la cause moyenne linéaire en temps des algorithmes (pour le diamètre d'un ensemble fini) dans une meilleure lumière, ainsi que le contraste de multiples dimensions et plan de problèmes de géométrie.
En 1983 Megiddo a donné un déterministe linéaire en temps de l'algorithme pour le plus petit cercle en joignant (ou de la sphère dans les dimensions supérieures).
En général la position de l'affichage de cercle ont deux ou trois points sur sa frontière, et donc de trouver les deux plus éloignées peut être fait "à la moyenne" dans la constante de temps une fois que la sélection de cercle est connu. Dans les dimensions supérieures, le nombre de points en position générale nécessaire à la limite de la sphère augmente (D+1 points pour la dimension D), et en fait, le coût de calcul de la distance entre une seule paire de points augmente de façon linéaire avec la dimension.
Le sous-ensemble de points situés sur la délimitation du cercle ou de la sphère se trouve aussi dans le temps linéaire. Sur le plan théorique pire des cas, tous les points se trouvent sur la délimitation du cercle ou de la sphère, mais ce qui est plus stricte que d'avoir tous les points de l'enveloppe convexe. Si les points sur la sphère sont indépendamment perturbé, dire le long des lignes radiales, puis la position générale est assurée avec la probabilité 1, et d'un diamètre approximatif peut être trouvé à partir de seulement D+1 points sur la révision de la sphère englobante. Cet essai randomisé de rapprochement dépendance quadratique sur la dimension, mais seulement linéaire de la complexité en nombre de points.
Si les points situés sur un cadre cercle sont "triés" (cyclique, bien sûr), trouver la paire la plus éloignée à part peut être fait en temps linéaire, en invoquant le "unimodality" du cercle (ce qui signifie que les distances à partir d'un point fixe montée de façon monotone jusqu'à l'antipode, puis à l'automne) pour amortir le coût de calcul des distances. Malheureusement, le tri serait d'introduire une étape à O(n log n) le temps de la complexité, et cela s'avère être le pire des cas optimal pour connaître les méthodes déterministes dans le cas planaire.
En 2001 Ramos réussi à montrer un O(n log n) algorithme déterministe pour les trois dimensions des ensembles, mais la technique est tellement impliqué qu'une mise en œuvre peut être impossible ou plus lente que la force brute toutes les paires de recherche jusqu'à de très grands ensembles de données.
Pour les dimensions supérieures, de nombreux auteurs ont considéré randomisés ou approximative des algorithmes. Voir Piotr Indyk de la thèse (2000) pour approximative méthodes avec seulement polynôme de la dépendance sur la dimension, pour diverses proximité problèmes.
OriginalL'auteur hardmath
Comme mentionné dans cette réponse, vous êtes à la recherche de la "diamètre" de l'ensemble de N points, un problème connu dans le calcul de la géométrie. Il existe essentiellement deux étapes:
Trouver l'enveloppe convexe des points. Des algorithmes existent qui sont en O(N ln N), dans le pire des cas. Dans la pratique, QuickHull est généralement un choix rapide, bien que potentiellement O(N^2) le pire des cas. Le QHull mise en œuvre est commode d'appeler à partir de la ligne de commande. La bibliothèque CGAL fournit un Implémentation C++
Antipodal paires sur l'enveloppe convexe sont des candidats pour les points les plus éloignés. On peut effectuer une recherche sur le antipodal points à l'aide d'un algorithme de type La rotation des étriers en O(N) fois.
Le problème peut être généralisée à un de "plus éloigné paires" problème: pour chaque point
i, de trouver la plus lointainej---nous sommes maintenant à la recherche de N couples de points. La solution utilise à nouveau l'enveloppe convexe, mais maintenant, la deuxième partie peut être fait avec une la matrice de la recherche algorithme.OriginalL'auteur Kipton Barros
Pas vraiment - une approche commune est de regrouper en groupes, puis stocker les distances entre les clusters.
De cette façon, vous n'avez pas besoin de vérifier si une certaine house à New York, est la plus éloignée de Paris si vous avez déjà determiend que l'Australie est encore loin
OriginalL'auteur Martin Beckett
Voir Jean Feminella excellente réponse à cette question semblable. Vous devriez obtenir O(n log n) pour la moyenne des cas.
Intéressant, merci.
Vrai. Je serai d'accord avec Martin que le regroupement est d'une grande aide, j'utilise geohashing dans un certain nombre de geo des applications sensibles.
L'enveloppe convexe peut être calculé en temps O(n ln n) le pire des cas. Il prend O(n) le temps de trouver le diamètre de l'ensemble par une recherche sur le antipodal points de l'enveloppe convexe. Plus de détails dans ma réponse
OriginalL'auteur Roger
La distance de
AàBest la même que la distance deBàA. Vous pouvez facilement modifier l'algorithme afin d'éliminer la moitié des calculs de cette façon. Ça va encore êtreO(n^2)mais sera deux fois plus rapide.Qui est, au lieu de l'informatique toutes les éléments de la diagonale de la matrice de distance
P x P:vous pouvez calculer le triangle supérieur:
ou le triangle inférieur:
OriginalL'auteur Matt Ball
Je ne sais pas si mettre les points dans un index spatial et l'interrogation elle conduit à un O(n log n) de l'algorithme.
OriginalL'auteur Peter G.
Si vous effectuez cette requête souvent, mais les points ne change pas beaucoup, vous pouvez effectuer precalculations qui peut accélérer les choses.
Chaque point peut stocker le point le plus éloigné d'elle et vérifiez sur chaque point de plus, si le nouveau point est plus loin.
Lorsque vous interrogez-vous juste de passer par tous les points et de regarder leur mise en cache des points.
Vous vous retrouvez avec O(n) pour un nouveau point d'entrée et de O(n) pour les plus éloignées de la requête.
OriginalL'auteur Variant