Effiziente Datenstruktur für den nächstgelegenen euclideanischen Abstand

Question

Die Frage ist inspiriert von dem folgenden UVA-Problem: https : //onlinejudge.org/index.php? Option= OnlineJudge & Amp; ItemID= 99999999 & Kategorie= 18 & Page= Show_Problem & Problem= 1628 .

Ein Netzwerk von autonomen, batteriebetriebenen Datenerfassungsstationen wurde installiert, um das Klima in der Region von Amazon zu überwachen. Eine Bestell-Dispatch-Station kann die Übertragung von Anweisungen an die Steuerstationen einleiten, damit sie ihre aktuellen Parameter ändern. Um die Überlastung der Batterie zu vermeiden, kann jede Station (einschließlich der Bestell-Versandstation) nur an zwei andere Stationen übertragen. Die Destinaturen einer Station sind die beiden nächstgelegenen Stationen. Im Falle von Unentschieden heißt das erste Kriterium, das westlichste (links auf der Karte) auszuwählen, und das zweite Kriterium ist, den südlichsten (niedrigsten auf der Karte) auszuwählen. Sie werden von der Amazon State Government in Auftrag gegeben, ein Programm zu schreiben, das entscheidet, ob bei der Lokalisierung der einzelnen Station alle Stationen alle Stationen erreichen können.

Der naive Algorithmus würde natürlich ein Diagramm mit Stationen als Scheitelpunkte erstellen und die Kanten aus einem bestimmten Scheitelpunkt berechnen, indem er alle anderen Scheitelpunkte für die nächsten zwei sucht. Dann können wir nur DFS / BFS ausführen. Natürlich dauert dies $ O (V ^ 2) $ Zeit, um die Grafik zu erstellen (was die Testfälle übergeben). Meine Frage ist jedoch, wenn wir den Graphen mit einer entsprechenden Datenstruktur schneller erstellen können. Insbesondere mit einem beliebigen Abfragepunkt $ P $ und einem bestimmten Satz von Punkten $ s $ können wir Organisieren Sie die Punkte in $ s $ so, dass wir schnell die beiden nächstgelegenen Punkte in $ S $ finden können bis $ P $ (sagen Sie in $ \ log v $ y $?). .

Answer 1

Wenn ich dies richtig verstehe, könnten die meisten räumlichen Indizes verwendet werden.

räumliche Indizes haben typischerweise über $ O (log {v}) $ Insertionszeit und ähnliche Nachbaraufzeit für die nächsten Nachbarn. Natürlich können Sie ein Voronoi-Diagramm aus dem erstellen, aber Sie können den Index auch direkt verwenden, um die nächstgelegenen Nachbarn zu finden, wenn Sie sie benötigen.

Für niedrige Dimensionalität (2D, 3D), die gemeinsamen Familien der räumlichen Indizes sind kd-bäume (ziemlich einfach und allgemein gut, aber neigen dazu, Probleme mit dichten Clustern von Punkten zu haben), quadrehee (ein bisschen schwieriger, sich selbst umzusetzen, weil numerische Präzision schwierig sein kann) und r-baum (am stärksten zu implementieren, aber geben Sie die beste garantierte Leistung, insbesondere den R * -Baum (R-Star-Tree)).

Wenn Sie C ++ verwenden, haben Sie einen Blick auf libsspatialindex oder der Boost R-Tree . Wenn Sie Java verwenden, werfen Sie einen Blick auf meine tinspin -Bibliothek.

Der technische Begriff dafür ist " $ K $ Nächster Nachbarabfragen" oder " $ K $ -NN Abfragen ", mit $ K $ In Bezug auf die Anzahl der nächsten Nachbarn, die Sie finden möchten.

Answer 2

Es scheint, dass die relevante Datenstruktur möglicherweise ein dynamisches voronoi-Diagramm .

.

Voronoi-Diagramme sind oft die Antwort, wenn ein Satz von Punkten in der Ebene beteiligt ist.

In diesem Fall, da sich der Punktsatz entwickelt, möchten Sie eine dynamische Version.