Tri par distance euclidienne

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

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

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

cg.comp-geom sorting Alex K.
la source

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

$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:

Solution 1: Trouvez les bissectrices perpendiculaires entre les paires de points et construisez la disposition de ces lignes. L'arrangement a 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 et le temps de requête est $\Theta(n^2)$ $\Theta(n^4)$ $O(n^4)$ . $O(\log n)$

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 de cellules, chacune avec une probabilité élevée est traversée par 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 . $\Theta(n)$ $\Theta(n^2)$ $O(n)$ $O(n^3)$

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 à où est le nombre de points qui sont en désordre avec le point . Mais est (chaque bissectrice non échantillonnée provoque au plus une paire de points dans le désordre), donc le temps de requête $\sum_i O(1+\log k_i)$ $k_i$ $y_i$ $\sum k_i$ $O(n)$ est également . $\sum_i O(1+\log k_i)$ $O(n)$

David Eppstein
la source

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

points de départ en temps

et stocker les résultats dans une table de hachage en utilisant l'espace

pour une recherche constante?

n^{4}

$n^4$

n

$n$

O (n^{2} \log n)

$O(n^2\log n)$

O (n^{2})

$O(n^2)$

Dave

Parce qu'il ya

points de départ avec les ordres de tri différents, non

Θ (n^{4})

$\Theta(n^4)$

Θ (n^{2})

$\Theta(n^2)$

David Eppstein

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 et ainsi trouver «votre» région par n'importe quelle technique de recherche significative prendra temps. ( MODIFIER: $n\log(n)$ $O(n!)$ $O(\log(n!)) = O(n\log(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

Θ (n^{4})

$\Theta(n^4)$

O (n!)

$O(n!)$

Θ (n^{2})

$\Theta(n^2)$

@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