Tri par distance euclidienne

17

est un ensemble de points sur un plan. Un point aléatoire x S est donné sur le même plan. La tâche consiste à trier tous les y S par distance euclidienne entre x et y .SxSySxy

Une approche sans cerveau consiste à calculer les distances entre et y pour tous les y S , puis à les trier à l'aide de n'importe quel algorithme rapide.xyyS

Existe-t-il un moyen de stocker ou de prétraiter pour accélérer le processus de tri?S

Alex K.
la source
1
Vous pouvez considérer une grille de taille appropriée et regrouper les points par carré correspondant (en utilisant, par exemple, une table de hachage). Ensuite, pour certaines paires de carrés, vous pouvez déduire que tous les points d'un carré sont plus éloignés de que tous les points d'un autre carré. En pratique, cela pourrait aider, je suppose. X
ilyaraz
«L'approche sans cerveau» que vous avez déclarée fonctionne en temps O (n log n), où n est le nombre de points dans S, ce qui, je suppose, est assez rapide dans la pratique. Voulez-vous désactiver le facteur log n, ou voulez-vous autre chose comme le tri externe ?
Tsuyoshi Ito
Le fait est que j'ai un temps pratiquement illimité pour préparer mon ensemble de points, mais le temps pour les trier est très limité. Cela dit, toute accélération du tri standard est appréciée - même s'il s'agit du même O (n log n), mais plus rapide dans le pire des cas (ou dans le meilleur des cas, ou autre).
Alex K.
Par exemple, si je stocke S comme un arbre 2D, je peux trouver un voisin le plus proche en temps O (log n). Il existe peut-être une solution similaire pour ma tâche. Je ne suis pas un grand expert des structures de données spatiales - et il y en a tellement - je pourrais facilement le manquer.
Alex K.

Réponses:

13

Solution 1: Trouvez les bissectrices perpendiculaires entre les paires de points et construisez la disposition de ces lignes. L'arrangement a thetav ( n 4 ) cellules, dans lequel l'ordre de tri est constante. Construisez donc une structure de données d'emplacement de point pour l'arrangement et décorez chaque cellule avec l'ordre trié qui doit être renvoyé pour les points de cette cellule. Les ordres triés entre les cellules adjacentes ne diffèrent que dans une seule transposition, vous pouvez donc utiliser une structure de données persistante pour permettre aux représentations de ces ordres triés de partager l'espace. L'espace total est O ( n 4 ) et le temps de requête est OΘ(n2)Θ(n4)O(n4) .O(Journaln)

Solution 2: choisissez un échantillon aléatoire de de ces mêmes bissectrices perpendiculaires, construisez leur arrangement et partitionnez chaque cellule d'arrangement par des segments de ligne verticale à travers chaque croisement de deux lignes échantillonnées. La partition résultante a Θ ( n 2 ) de cellules, chacune avec une probabilité élevée est traversée par O ( n ) non échantillonnés bissectrices. Décorez chaque cellule de la partition par un ordre trié valide des points vus de certains x dans la cellule. L'espace total est O ( n 3 ) .Θ(n)Θ(n2)O(n)O(n3)

Maintenant, pour effectuer une requête, localisez le point de requête dans la partition, recherchez l'ordre stocké avec la cellule de partition et utilisez l' algorithme de tri par comparaison d' arbre cartésien de Levcopoulos et Petersson (1989) en commençant par cet ordre stocké. Le temps pour cette étape est proportionnel à k i est le nombre de points qui sont en désordre avec le point y i . Mais k i est O ( n ) (chaque bissectrice non échantillonnée provoque au plus une paire de points dans le désordre), donc le temps de requêtejeO(1+Journalkje)kjeyjekjeO(n) est également O ( n ) .jeO(1+Journalkje)O(n)

David Eppstein
la source
1
PS: voici une variante alternative de la solution 2 qui utilise le même espace et le même temps de requête mais troque un algorithme de prétraitement plus compliqué pour un algorithme de requête plus simple: 11011110.livejournal.com/233793.html
David Eppstein
Pourquoi faire un prétraitement alors que vous pouvez trier à partir de tous les n points de départ en temps O ( n 2 log n ) et stocker les résultats dans une table de hachage en utilisant l'espace O ( n 2 ) pour une recherche constante? n4nO(n2Journaln)O(n2)
Dave
Parce qu'il ya points de départ avec les ordres de tri différents, non Θ ( n 2 ) . Θ(n4)Θ(n2)
David Eppstein
1

Vous ne pourrez probablement pas vous éloigner de fois de la façon dont vous le découpez; même le précalcul des régions correspondant à tous les ordres de tri possibles pourrait (je crois) produire des régions O ( n ! ) et ainsi trouver «votre» région par n'importe quelle technique de recherche significative prendra O ( log ( n ! ) ) = O ( n log ( n ) ) le temps. ( MODIFIER:nJournal(n)O(n!)O(Journal(n!))=O(nJournal(n))c'est absolument faux; voir l'excellente réponse de David Eppstein pour plus d'informations!) Un moyen utile de réduire la complexité, d'autre part - surtout si vous n'avez pas besoin du tri complet à la fois mais que vous devez simplement pouvoir retirer aléatoirement le ème le plus proche à la volée - peut - être par des schémas d'ordre supérieur Voronoï: extensions de la cellule standard Voronoi qui ACCUEILLENT non seulement le voisin le plus proche , mais la deuxième plus proche, etc. Frank papier de Dehne sur la recherche de k-plus proche voisin, http: //people.scs .carleton.ca / ~ dehne / publications / 2-02.pdf semble être la référence canonique; sa page d'accueil à http://www.dehne.carleton.ca/publications contient un certain nombre d'autres articles sur les diagrammes de Voronoi qui pourraient être utiles.k

Steven Stadnicki
la source
3
Θ(n4)O(n!)Θ(n2)
@David Je pense que vous devriez en faire une réponse.
James King
Appuyé - n! me sentais mal quand je l'écrivais, mais je ne pouvais pas voir de cas contre. Je vais modifier ma réponse sous peu pour corriger cela, mais j'aimerais vraiment en voir une plus directement informée; Merci!
Steven Stadnicki