Structure de données efficace pour la distance euclidienne la plus proche

Question

La question est inspirée du problème UVA suivant: HTTPS : //onlinejudge.org/index.php? Option= OnlineJudge & itemID= 99999999 & Catégorie= 18 & Page= show_problem & problème= 1628 .

Un réseau de stations d'acquisition de données autonomes, alimentées par batterie, a été installée pour surveiller le climat de la région d'Amazon. Une station de distribution de commande peut initier une transmission d'instructions aux stations de contrôle afin de modifier leurs paramètres actuels. Pour éviter de surcharger la batterie, chaque station (y compris la station de distribution de commande) ne peut transmettre que dans deux autres stations. Les destinataires d'une station sont les deux stations les plus proches. En cas de tirage au sort, le premier critère est de choisir l'ouest la plus ouest (sur la carte), et le deuxième critère consiste à choisir le plus au sud (le plus bas sur la carte). Vous êtes commandé par le gouvernement de l'État Amazon à écrire un programme qui décide si, étant donné la localisation de chaque station, les messages peuvent atteindre toutes les stations.

L'algorithme naïf de bien sûr construirait un graphique avec des stations comme des sommets et calculerait les bords d'un sommet donné en cherchant à travers tous les autres sommets des deux les plus proches. Ensuite, nous pourrions simplement exécuter dfs / bfs. Bien sûr, cela prend $ o (v ^ 2) $ temps pour construire le graphique (qui passe les cas de test). Ma question, cependant, est si nous pouvons créer le graphique tout plus rapidement avec une structure de données appropriée. Spécifiquement, donné un point de requête arbitraire $ p $ et un ensemble donné de points $ s $ , pouvons-nous Organisez les points dans $ S $ de telle manière que nous pouvons trouver rapidement les deux points les plus proches de $ S $ à $ p $ (disons, dans $ \ journal v $

Answer 1

Si je comprends cela correctement, la plupart des index spatiaux peuvent être utilisés.

Les index spatiaux ont généralement environ $ o (log {v}) $ temps d'insertion et temps de recherche similaire pour les voisins les plus proches. Bien sûr, vous pouvez créer un diagramme Voronoi à partir de cela, mais vous pouvez également utiliser l'index directement pour trouver les voisins les plus proches chaque fois que vous en avez besoin.

Pour la faible dimension (2D, 3D), les familles communes d'index spatiaux sont KD-Trees (assez simple et généralement bon, mais a tendance à avoir des problèmes avec des grappes denses de points), Quadtrees (un peu plus difficile à mettre en œuvre car la précision numérique peut être délicate) et R-Tree (le plus difficile à mettre en œuvre, mais donner la meilleure performance garantie, en particulier l'arbre R * (R-Star-Star-Tree)).

Si vous utilisez C ++, consultez libspatialIndex ou Boost R-Tree . Si vous utilisez Java, consultez mon Bibliothèque Tinspin .

Le terme technique pour cela est " $ K $ requêtes de voisin le plus proche" ou " $ k $ -Nn des requêtes ", avec $ K $ faisant référence au nombre de voisins les plus proches que vous souhaitez trouver.

Answer 2

Il semble que la structure de données pertinente pourrait être une dynamique Voronoi Diagram .

Les diagrammes de Voronoi sont souvent la réponse lorsqu'un ensemble de points sur l'avion est impliqué.

Dans ce cas, puisque l'ensemble de points évolue, vous voulez une version dynamique.