Durchführungskosten ca. Suche nach dem nächsten Nachbarn in einem Quadtree überspringen

HINWEIS : Die Frage wurde in meinen Antworten angepasst: Unter der Annahme, dass wir jetzt die niedrigsten Geschwistervorfahren in -Zeit finden können, kann die ANN wirklich in ?O ( log n $O(1)$$O(\log n)$

Quadtrees sind effiziente räumliche Indizes. Ich habe ein Rätsel mit der Implementierung einer Suche nach dem nächsten Nachbarn in einer komprimierten Quadtree-Struktur, wie in [2] beschrieben. (Ohne auf Details einzugehen, erfolgt die Suche von oben nach unten entlang sogenannter äquidistanter Quadrate und endet am Endknoten eines äquidistanten Pfades. Im angehängten Bild kann dies einer der Knoten im Südosten sein, die mit Punkten gefüllt sind.)

Damit ihr Algorithmus funktioniert, muss für jeden Knoten - ein Quadrat mit mindestens zwei nicht leeren Quadranten - ein Zeiger für jeden niedrigsten (in der Hierarchie am nächsten gelegenen) Ahnenknoten in jeder der vier Richtungen (Nord, West, Süd) beibehalten werden , Osten). Diese werden durch die grünen Pfeile für den Vorfahren der Knoten nach Westen angezeigt (der Pfeil zeigt auf die Mitte des Ahnenquadrats).

Das Papier behauptet, dass diese Zeiger beim Einfügen und Löschen von Punkten in O (1) aktualisiert werden können. Wenn ich mir jedoch das Einfügen des grünen Punkts anschaue, muss ich anscheinend eine beliebige Anzahl von Zeigern aktualisieren, in diesem Fall sechs davon.

Ich hoffe auf einen Trick, um dieses Zeiger-Update in konstanter Zeit durchzuführen. Vielleicht gibt es eine Form der Indirektion, die ausgenutzt werden kann?

BEARBEITEN:

Der relevante Abschnitt aus dem Papier ist 6.3, wo er lautet: "Wenn der Pfad gebogen ist, sollten wir zusätzlich zu den niedrigsten Vorfahren von auch für jede der Richtungen die niedrigste berücksichtigen Vorfahr von , der in diese Richtung geht [...] Das Finden dieser Quadrate aus kann in Zeit pro Quadrat erfolgen, wenn wir jedem Quadrat in zusätzliche Zeiger die für jede Richtung auf seine nächsten Vorfahren zeigen Diese Zeiger können auch in -Zeit während des Einfügens oder Löschens eines Punkts aktualisiert werden. "$log(c/ε)$$q$$2^d$$q$$q$$O(1)$$2^d$$Q_0$$O(1)$

[2]: Eppstein, D. und Goodrich, MT und Sun, JZ, „The Skip Quadtree: Eine einfache dynamische Datenstruktur für mehrdimensionale Daten“, in Proceedings of the einundzwanzigsten jährlichen Symposium über Computergeometrie, S. 296–305 , 2005.

Wie David weiß ich nicht, warum Jonathan diese Bemerkung über die 2D-Zeiger gemacht hat. Sie werden nicht benötigt. Wie David oben erwähnt hat, ist die wesentliche Eigenschaft, dass es ausreicht, sich die Geschwisterknoten (und ihre Kästchen) im Überspringquadtree zu merken, wenn wir eine Punktposition zu einem Blatt v in Q_0 machen. Wenn wir ein Feld aus P verarbeiten, erstellen wir eine Punktposition für das Blattfeld, das unserem Abfragepunkt am nächsten liegt, und fügen die Geschwisterfelder ein, wenn wir nach unten gehen. Es klingt so, als würde dies mehr oder weniger Ihrer Antwort entsprechen. Darüber hinaus ist dieses Verfahren sehr ähnlich, wie beispielsweise die ungefähre Punktposition in der folgenden Veröffentlichung beschrieben wird: Arya, Sunil und Mount, David M. und Netanyahu, Nathan S. und Silverman, Ruth und Wu, Angela Y., "Ein optimaler Algorithmus für die ungefähre Suche nach nächsten Dimensionen des nächsten Nachbarn", JACM, 1998. In der Tat,

Man kann sich Quadt Quadtree als eine Skip-List-Implementierung einer Datenstruktur vorstellen, in der die Punkte gemäß ihrer Z-Reihenfolge gespeichert sind. Es ist (wohl) zumindest konzeptionell einfacher ...

Siehe Kapitel 2 hier: http://goo.gl/pLiEO .

Und ja, vorausgesetzt, Sie können einige grundlegende Operationen der Z-Ordnung in konstanter Zeit ausführen, können Sie ANN definitiv in logarithmischer Zeit ausführen. Das oben erwähnte Kapitel zeigt auch, dass es keine Möglichkeit gibt, bizarre Operationen zu vermeiden, wenn man komprimierte Quadtrees will. Beachten Sie, dass der LCA-Betrieb nicht erforderlich ist ...

Ich habe auch intuitiv das Gefühl, dass man ohne diese Zeiger leben könnte, und da ich irgendwann alle Knoten auf der Festplatte beibehalten muss, ist jede Reduzierung der Zeiger großartig.

Meine Idee lautet ungefähr wie folgt: Abgesehen vom besten Kandidatenpunkt (Blatt) verfolgen wir auch den schlechtesten Abstand in jeder Runde, . Ein schlechtester Abstand wäre das Maximum der Abstände aller Ecken eines Knotens zum Abfragepunkt , unabhängig davon, ob innerhalb eines Quadrats oder außerhalb liegt.$l_{best}$$r_{max}$${dist}'(v,q)$$q$$v$$v$

Eine Runde ist wie folgt: Wenn leer ist, geben Sie das , falls vorhanden. Andernfalls gibt delete-min den aktuellen in . Initialisieren Sie auf (oder setzen Sie es auf wenn noch kein bester Kandidat beobachtet wurde). Testen Sie zunächst jedes nicht leere Kind von in . Wenn dieses untergeordnete ein Blatt ist, aktualisieren Sie gegebenenfalls und . Wenn ein Knoten ist, berechnen Sie und , wobei letzterer der beste Abstand ist: Entweder Null, wennl b e s t p 0 Q 0 r m a x l b e s t ∞ p 0 Q 0 q l b e s t r m a x q d i s t ' ( q , v $P$$l_{best}$$p_0$$Q_0$$r_{max}$$l_{best}$$\infty$$p_0$$Q_0$$q$$l_{best}$$r_{max}$$q$${dist}'(q,v)$${dist}(q,v)$$v$ liegt innerhalb von oder dem kürzesten Abstand aller Ecken von zu .$q$$q$$v$

Wenn , vergiss , sonst behalte es. Wenn die Anzahl der Knoten gehalten wird , schieben diese Knoten auf . Ende der Runde.${dist}(q,v) > r_{max}$$q$$\geq 2$$P$

Andernfalls gehen Sie ähnlich wie bei der ursprünglichen Suche vor: Suchen Sie , den entsprechenden Knoten zu im höchstmöglichen , und beginnen Sie von dort aus: Anstatt nach einem Kind mit gleichem Abstand zum Abstieg zu fragen, testen Sie alle Kinder gemäß dem vorherigen Verfahren Überspringen Sie also diejenigen, deren bester Abstand überschreitet . Wenn nach diesem Test ein Kind übrig geblieben ist, steigen Sie darauf hin und wiederholen Sie den Vorgang. Wenn kein Kind mehr übrig ist, gehen Sie zu und wiederholen Sie den . Wenn der Test in , ist die Runde beendet.$q$$p_0$$Q_j$$r_{max}$$Q_{j-1}$$Q_0$

Im Moment weiß ich weder, ob dies garantiert, dass in jedem möglichen Fall der nächste Nachbar gefunden wird, noch dass es so gut funktioniert wie der ursprüngliche Algorithmus. Auch wenn die Initialisierung von ausreichend ist oder nicht. Und was sollte die Priorität in - immer noch die beste Entfernung?$r_{max}$$P$

EDIT (April 2013)

Ich habe jetzt weitere Experimente mit einer Klarstellung des obigen Algorithmus durchgeführt, bei dem eine Definition von "äquipotenten" Knoten anstelle von äquistabierenden Knoten verwendet wird, basierend auf der Eigenschaft, dass der Abstieg zu einem solchen Knoten den Bereich, der von der aktuellen Abfrageform der Ausdehnung abgedeckt wird, nicht ändert .$r_{max}$

Leider kann man pathologische Fälle konstruieren (siehe Bild unten; Abfragepunkt ist unten in der Mitte), in denen sich die Leistung auf Runden verschlechtert .$O(\sqrt n)$

Ich habe jetzt den auf Equistabbing basierenden Algorithmus implementiert, bei dem die Vorfahren der niedrigsten Geschwister mit Brute-Force durchsucht werden (bevor versucht wird, eine O (1) -Variante zu finden), um die maximale Anzahl der in Satz 13: beanspruchten Runden) zu überprüfen .$O(\epsilon^{1−d}(\log n+\log \epsilon^{−1}))$

Ich verwende das "pathologische" Beispiel aus meiner vorherigen Antwort. Das zweidimensionale Wurzelquadrat hat eine Seitenlänge von 512, wobei die Mittelkoordinate (256, 256) ist. Koordinaten werden in ganzen Zahlen angegeben, was zu einem direkten . Die Punkte sind gleichmäßig horizontal über dem Wurzelquadrat verteilt, und der Abfragepunkt liegt bei (256, 511) (beachten Sie, dass 512 bereits außerhalb des Wurzelquadrats liegt).$\epsilon = 1$$v$

In der folgenden Abbildung ist der vollständige Baum dargestellt, und die Anzahl der Punkte in diesem Beispiel beträgt 16. Die blauen quadratischen Umrisse geben die interessanten Quadrate an, die in die Prioritätswarteschlange verschoben werden, und die Ziffern in ihrer Mitte geben die runde Zahl in an was sie geschoben werden. Entdeckte Blattpunkte sind auch mit der runden Nummer gekennzeichnet, in der sie berücksichtigt werden. Die drei transparenten blauen Kreise geben den bekannten NN-Radius nach der 1., 2. und 7. Runde an (der nächste Nachbar wird zuerst in der 7. Runde gesehen). Insgesamt gibt es 12 Runden (die letzten 6 nur Pop-Quadrate aus der Warteschlange, aber keine neuen Quadrate hinzufügen).$Q_0$

Ich habe dieses Beispiel mit einer Reihe von immer größeren Wurzelquadraten und einer Anzahl von Punkten ausgeführt, wobei der Abstand der Punkte gleich blieb (32). Dies bestätigte, was aus der Abbildung bereits intuitiv ersichtlich ist: Der Algorithmus benötigt -Runden, während Satz 13 mit und besagt, dass nur -Runden benötigt würden.d=2ϵ=1O(logn$O(\sqrt n)$$d = 2$$\epsilon = 1$$O(\log n)$

Wenn mir also nichts Entscheidendes fehlt, kann der Algorithmus die angegebene Geschwindigkeit nicht erreichen. Irgendwelche Kommentare oder Ideen?