Compte tenu d'un ensemble de n points dans le plan, je veux prépraquer ces points en quelque sorte plus vite que O (n ^ 2) (O (NLog (n)) de préférence), puis être capable de répondre aux requêtes du type suivant "Combien de n points n sont à l'intérieur d'un cercle avec un centre donné et un rayon?" plus rapide que O (n) (O (journal (n) de préférence).
Pouvez-vous suggérer une structure de données ou une algorithme que je peux utiliser pour ce problème?
Je sais que de tels types de problèmes sont souvent résolus à l'aide de diagrammes de Voronoi, mais je ne sais pas comment l'appliquer ici.
6 Réponses :
Construire un KD-Tree des points, cela devrait vous donner une bien meilleure complexité que o (n), en moyenne O (log (n)), je pense.
Vous pouvez utiliser un arbre 2D car les points sont contraints à un avion.
supposant que nous avons transformé le problème en 2D , nous aurons quelque chose comme celui-ci pour les points: alors vous appelez cette fonction avec la racine de l'arborescence KD plus grand et moins contient des points avec plus et moindre Coordonnées respectivement sur le SplitAxis.
Les kd-arbres sont souvent utiles, mais je ne vois pas comment ils peuvent aider dans ce cas. Pourriez-vous expliquer?
Merci pour votre réponse Andreas. Votre code trouve tous les points à l'intérieur du cercle, alors je pense que cela ne peut pas être plus rapide que O (log (n) + k), où k est la réponse. Mais je n'ai besoin que du nombre k, pas des points. En fait, je sais comment le modifier. Nous devons stocker la taille de la sous-arbre dans chaque nœud, et si tous les points possibles à l'intérieur du sous-arbre se trouvent à l'intérieur du cercle, nous ajoutons simplement la taille du sous-arbre à la réponse sans traverser le sous-arbre. Mais je ne suis pas sûr que cela sera meilleur que O (n) dans le pire des cas.
En supposant que vous avez un ensemble de points S dans un plan cartésien avec des coordonnées (x i sub>, y i sub>), donné un cercle arbitraire avec centre (x Je suppose également que les points et le cercle peuvent bouger de sorte que certaines structures statiques Cela peut accélérer cela ne sera pas nécessairement approprié. p> Trois choses à l'esprit qui peut accélérer cela: P> Tout d'abord, vous pouvez vérifier: P> sqrt((xi-xc)^2 + (yi-yc)^2) <= r
Seule la dernière suggestion change effectivement la durée de fonctionnement asymptotique.
Oui, mais la dernière suggestion n'a aucun sens en dehors du contexte des deux autres.
Cet algorithme a toujours un cas de fonctionnement du pire des cas de O (n).
(Dites que tous les points ont la même valeur y et vous avez choisi de trier par Y)
Bonne chance de trouver une solution sub-O (n) à ce problème dans le pire des cas.
N'oubliez pas que la recherche dans une carte Java ou un dictionnaire C # est O (n) dans le pire des cas. C'est juste que le pire des cas est plutôt improbable, de sorte que de telles structures soient citées comme étant "près de O (1)" d'accès en tant que cas exact en supposant une distribution de hachage semi-normale. Ce problème doit également être approché d'un point de vue prévu sur une répartition réaliste des points.
Même en fonction de la distribution totalement uniforme des points, cet algorithme n'est pas O (log (n)). Vous ne pouvez pas utiliser de carte de hachage pour votre algorithme, vous avez besoin d'une carte commandée comme std :: map où vous pouvez trouver la plage valide dans O (log (n)), pas O (1 ) temps.
Et lorsque vous avez la gamme, vous aurez-le (probablement) inclure plus d'un point, combien de bien sûr dépend du rayon du cercle.
Merci cloretus. Je comprends votre idée, mais elle est toujours trop lente si, par exemple, tous les points n sont à l'intérieur du cercle et que tous les points ont des coordonnées distinctes X et Y.
Pourquoi cela a-t-il eu des upvotes? Il ne donne aucune suggestion pratique (valide) pour résoudre le problème.
Selon la quantité de temps précalcules que vous avez, vous pouvez construire un arbre comme celui-ci:
Les branches de premier nœud sont des valeurs X, ci-dessous sont des nœuds de valeur Y, et ci-dessous sont des nœuds de valeur rayon. à chaque feuille est un hashset de points.
Lorsque vous souhaitez calculer les points sur X, Y, R: Passez dans votre arbre et descendez la branche qui correspond à vos valeurs X, Y le plus proche. Lorsque vous descendez au niveau de la racine, vous devez faire un petit match (Time Constat), mais vous pouvez trouver un rayon de telle sorte que tous les points de ce cercle (définis par le chemin dans l'arborescence sont à l'intérieur du cercle spécifié. par x, y, r et un autre cercle (même x_tree, y_tree dans l'arbre comme avant, mais différent R_TREE) de sorte que tous les points du cercle d'origine (spécifiés par X, Y, R) sont dans ce cercle. < / p>
à partir de là, passez à travers tous les points dans le plus grand des deux cercles d'arborescence: si un point est dans le plus petit cercle, ajoutez-le aux résultats, sinon, exécutez la distance de la distance.
seul problème est qu'il faut très longtemps pour précomputer l'arbre. Bien que vous puissiez spécifier le temps que vous souhaitez dépenser en modifiant le nombre de branches X, Y et R que vous souhaitez avoir dans votre arbre.
Construisez une structure de subdivision spatiale telle qu'un quadtree ou kd-arbre des points. À chaque nœud, stockez la quantité de points couverts par ce nœud. Ensuite, lorsque vous devez compter les points couverts par le cercle de recherche, traverser l'arborescence et pour chaque subdivision dans un chèque de nœud si elle est complètement en dehors du cercle, puis ignorez-la si elle est complètement à l'intérieur du cercle, puis ajoutez son comptage à la Total s'il intersecte avec le cercle, recueil, lorsque vous arrivez à la feuille, vérifiez le (s) point (s) à l'intérieur de la feuille de confinement.
Ceci est toujours o (n) le pire des cas (par exemple si tous les points se trouvent sur le périmètre du cercle) mais le cas moyen est O (log (n)).
Ok, on dirait qu'il n'y a aucun moyen de le faire plus vite que O (n) dans le pire des cas. Ensuite, O (journal (n)) en moyenne sera probablement suffisant pour moi. Merci!
J'ai ajouté une implémentation prête à utiliser à l'aide de KD Tree ici - Leetcode.com/problems/...
Si mon objectif est de la vitesse et que le nombre de points n'était pas énorme (des millions, je me concentrerais sur l'empreinte de la mémoire autant que la complexité algorithmique.
Un arbre k-D déséquilibré est le meilleur sur papier, mais il nécessite des pointeurs, qui peuvent étendre l'empreinte de mémoire par 3x +, de sorte qu'il est sorti.
Un arbre K-D équilibré ne nécessite aucun stockage, autre que pour un tableau avec un scalaire pour chaque point. Mais cela a aussi une faille: les scalaires ne peuvent pas être quantifiés - ils doivent être les mêmes 32 bits flottant que dans les points d'origine. S'ils sont quantifiés, il n'est plus possible de garantir qu'un point qui apparaisse plus tôt dans le tableau est soit sur le plan de fractionnement, soit à sa gauche et qu'un point qui apparaît plus tard dans la matrice est soit sur le plan de fractionnement, soit à sa droite.
Il existe une structure de données que j'ai développée qui répond à ce problème. Le Synergetics Les gens nous disent que le volume est expérimentalement quatre direction. Disons qu'un avion est également expérimenté expérimenté trois direction.
Nous sommes habitués à traverser un avion par les quatre directions -X, + x, -y, et + y, mais il est plus simple d'utiliser les trois directions A, B et C, qui pointent aux sommets d'un triangle équilatéral.
Lorsque vous construisez l'arbre k-D équilibré, projetez chaque point sur les axes A, B et C. Trier les points en augmentant A. Pour le point médian, arrondi, quantifier et stocker un. Ensuite, pour les sous-tableaux à gauche et à droite de la médiane, trier en augmentant B et pour les points médians, rond-point, quantifier et stocker b. Recueil et répétez jusqu'à ce que chaque point ait stocké une valeur.
Puis, lorsque vous testez un cercle (ou autre) contre la structure, calculez d'abord les coordonnées maximum A, B et C du cercle. Ceci décrit un triangle. Dans la structure de données que nous avons faite dans le dernier paragraphe, comparez la coordonnée du point médian à la coordonnée maximale du cercle. Si le point A est plus grand que le Circle A, nous pouvons disqualifier tous les points après la médiane. Ensuite, pour les sous-tableaux à gauche et à droite (si non disqualifié) de la médiane, comparez le Circle B à la coordonnée B de la médiane du point. Recueil et répétez jusqu'à ce qu'il n'y ait plus de points à visiter.
Ceci est similaire dans un thème au Structure de données BiH , mais ne nécessite aucun intervalle de - x et + x and -y and + y, car A, B et C sont aussi bons pour traverser l'avion et nécessiter une direction en moins de le faire.
J'ai utilisé le code de Andreas mais il contient un bug. Par exemple, j'ai eu deux points sur le plan [13, 2], [13, -1] et mon point d'origine était [0, 0] avec un rayon de 100. Il ne trouve que 1 point. Ceci est mon correctif:
void findPoints(Node * root, vector<Node*> & result, Node * origin, double radius, int currAxis = 0) {
if (root) {
if (pow((root->coords[0] - origin->coords[0]), 2.0) + pow((root->coords[1] - origin->coords[1]), 2.0) < radius * radius) {
result.push_back(root);
}
if (root->coords[currAxis] - origin->coords[currAxis] > radius) {
findPoints(root->right, result, origin, radius, (currAxis + 1) % 2);
return;
}
if (origin->coords[currAxis] - root->coords[currAxis] > radius) {
findPoints(root->left, result, origin, radius, (currAxis + 1) % 2);
return;
}
findPoints(root->right, result, origin, radius, (currAxis + 1) % 2);
findPoints(root->left, result, origin, radius, (currAxis + 1) % 2);
}
}
Vous pouvez probablement bien faire bien dans le cas attendu, mais je serais surpris si vous obtenez la pire performance des requêtes sous O (n). Les pires cas que je pensais sont beaucoup de points très proches du cercle donné.
@Jason, dans ce cas, la complexité requise est O (logn + k), où K est le nombre de points à l'intérieur du cercle. C'est en fait une tâche commune des devoirs dans un cours de géométrie informatique :)
Dans le sens des diagrammes de Voronoi, si vous dessinez tous les bisecteurs perpendiculaires entre points, qui est O (n ^ 2) et identifiez toutes les régions que vous avez apportées (également O (N ^ 2), selon RECHERCHE.ATT.com/~njas/Sprocences/a000124 ), alors tous les points de Chaque région partage la même séquence de points par ordre de distance, non? Donc, pour chaque région, faites une structure de données pour résoudre le problème dans cette région. Cela ferait la phase 2 O (log n). Mais c'est une quantité de travail ridicule dans la phase 1, je suppose O (n ^ 3 log n).
@Anna, heh, qui change le problème plutôt beaucoup.
@Anna Pouvez-vous dire quelle est la solution commune pour l'affectation commune des devoirs que vous avez mentionnée. Bien que j'ai besoin plus rapide que l'algorithme O (k), mais cela peut toujours être utile.
@Jason, n est grand, donc je ne peux pas me permettre O (n ^ 3 journal n), même o (n ^ 2) est trop.