3.1 Algorithmen auf der Basis der logarithmischen Methode
Die ersten Algorithmen basieren auf der Anwendung der logarithmischen Methode von Bentley. Diese Anwendung erschien zuerst bei Smid . (Siehe auch Schwarz.)
S sei S die aktuelle Punktmenge in ℝD, und n bezeichne ihre Größe. Schreibe n im binären Zahlensystem, n=∑i≥0ai2i, wobei ai ∈ {0,1}. Unterteile S (beliebig) in Teilmengen: Für jedes i, das ai = 1 ist, gibt es eine Teilmenge Si mit der Größe 2i. Außerdem gibt es für jedes solche i eine reelle Zahl δi, so dass d(S) ≤ δi ≤ d (Si) die Datenstruktur aus dem Folgenden besteht.
(1)
Das nächstgelegene Paar von S und sein Abstand δ
(2)
Für jedes i, so dass ai = 1, ein δi -Gitter, das die Punkte von Si speichert. Wir nehmen an, dass die nicht leeren Zellen dieses Gitters in einem balancierten binären Suchbaum gespeichert sind, lexikographisch sortiert nach ihren „unteren linken“ Ecken.
Betrachten wir nun das Einfügen eines neuen Punktes p. Für jedes i, so dass ai = 1 ist, finden wir die Zelle des δi-Gitters, die p zusammen mit den 3D – 1 benachbarten Zellen enthält. Dann berechnen wir die Abstände zwischen p und allen Punkten von Si, die in diesen Zellen enthalten sind. Wenn wir einen Abstand finden, der kleiner als δ ist, dann aktualisieren wir δ und das nächstgelegene Paar. Nun muss noch der Rest der Datenstruktur aktualisiert werden. Sei j der Index, so dass a0 = a1 = … = aj – 1 und aj = 0. Sei Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 und δj := δ. Wir bilden ein δj -Gitter für die Menge Sj und verwerfen die Gitter für die Menge S0, S1, … Sj – 1 (wodurch diese Mengen implizit leer werden).
Um die Korrektheit dieses Algorithmus zu beweisen, ist zu beachten, dass, da d(S) ≤ δi ist, es ausreicht, p mit allen Punkten von Si zu vergleichen, die sich in der Nachbarschaft von p im δi-Gitter befinden. Das engste Paar wird also korrekt aktualisiert. Außerdem erfüllt der neue Wert Sj die Bedingung d(S ∪ {p}) ≤ δj ≤ d(Sj), und für alle i > j haben wir d(S ∪ {p} ≤ δi d(Si). Schließlich enthält die aktualisierte Datenstruktur ein Gitter, das 2i Punkte für jedes i speichert, so dass die binäre Darstellung von n + 1 eine Eins an der Position i enthält.
Wir analysieren die Komplexität des Einfügungsalgorithmus. Zunächst ist zu beachten, dass, da δi ≤ d(Si) ist, die Nachbarschaft von p im δi -Gitter höchstens eine konstante Anzahl von Punkten von Si enthält. Daher benötigen wir für jedes Gitter O(log n) Zeit. Da die Datenstruktur eine logarithmische Anzahl von Gittern enthält, benötigt der erste Teil des Einfügungsalgorithmus O(log 2n) Zeit.
Betrachten wir den zweiten Teil des Algorithmus, in dem wir das δj -Gitter aufbauen. Dieser Schritt benötigt wegen der Sortierung O(|Sj |log |Sj|) Zeit. Wenn wir die Punkte jedoch in einer geeigneten sortierten Reihenfolge speichern, kann dieses Gitter in O(|Sj|) = O(2j) Zeit aufgebaut werden. (Siehe Details.) Da j jeden Wert zwischen Null und ⌊log n⌋ annehmen kann, schwankt die Einfügezeit stark. Wir behaupten jedoch, dass die amortisierte Zeit für den zweiten Schritt durch O(log n) begrenzt ist.
Um diese Behauptung zu beweisen, nehmen wir an, wir beginnen mit einer leeren Menge S und führen eine Folge von n Einfügungen durch. Sei kj die Anzahl der Male, die wir während dieser Einfügungen ein Gitter für eine Teilmenge der Größe 2j bilden. Dann ist kj höchstens gleich der Anzahl der ganzen Zahlen, die aus höchstens 1 + ⌊log n⌋ Bits bestehen, deren j niederwertigsten Bits gleich eins sind und deren (j + 1)-stes Bit gleich null ist. Das heißt, wir haben
Die Gesamtzeit für den zweiten Schritt während der n Einfügungen ist begrenzt durch
was die Behauptung beweist.
Wir haben gezeigt, dass die Laufzeit des gesamten Algorithmus zur Erhaltung des engsten Paares durch O(log 2n) Worst-Case-Zeit plus O(log n) amortisierte Zeit pro Einfügung begrenzt ist. Mit Hilfe von Standardtechniken (siehe Overmars) können wir die Datenstruktur so transformieren, dass der zweite Schritt im schlimmsten Fall logarithmische Zeit benötigt. Somit haben wir eine Datenstruktur, die das engste Paar in O(log 2n) Worst-Case-Zeit pro Einfügung verwaltet. Die Struktur hat die Größe O(n).
Beachten Sie, dass der erste Schritt des Algorithmus O(log 2n) Zeit benötigt, während der zweite Schritt nur O(log n) Zeit benötigt. Dies deutet darauf hin, dass eine Verbesserung möglich ist. Anstatt n im binären Zahlensystem zu schreiben, verwenden wir das Zahlensystem mit der Basis log n. (Siehe Overmars oder Schwarz.) Auf diese Weise benötigen beide Schritte O(log 2n/log log n) Zeit, während der benötigte Platz linear bleibt.
Damit haben wir eine Datenstruktur von linearer Größe, die das engste Paar in O(log2 n /log log n) Worst-Case-Zeit pro Einfügung verwaltet. Man beachte, dass der Algorithmus die Floor-Funktion verwendet, um die Gitterzelle zu finden, die den neuen Punkt p enthält. Indem man das Gitter durch ein degradiertes Gitter ersetzt, kann der Algorithmus im algebraischen Berechnungsbaummodell implementiert werden.
Es ist noch möglich, die obige Datenstruktur zu verbessern. Betrachten wir noch einmal die Datenstruktur, die auf der Darstellung von n im binären Zahlensystem basiert. Die wichtigste Beobachtung ist die folgende: Wenn wir einen Punkt p einfügen, dann finden wir für jedes i, so dass ai = 1 ist, die Zelle des δi -Gürtels, die p enthält (plus die benachbarten Zellen). Das heißt, wir führen Punktlokalisierungsabfragen in einer logarithmischen Anzahl von Gittern durch, aber immer mit demselben Abfragepunkt p. In Schwarz und Smid wird gezeigt, dass die fraktionale Kaskadentechnik so erweitert werden kann, dass alle diese Abfragen zusammen in O(log n log log n) Zeit gelöst werden können. Das Hauptproblem besteht darin, dass wir Netze mit unterschiedlichen Gittergrößen haben. Daher muss eine Ordnung für die Gitterzellen eingeführt werden, die mit all diesen Größen „kompatibel“ ist. Eine solche Ordnung ist definiert. Das Ergebnis ist, dass das Auffinden des Punktes p in allen Gittern O(log n) Vergleiche erfordert. Da die Anordnung jedoch recht kompliziert ist, benötigt jeder Vergleich O(log log n) Zeit. Insgesamt erhalten wir eine Datenstruktur der Größe O(n), die das nächstliegende Paar in O(log n log log n) amortisierter Zeit pro Einfügung verwaltet. Beachten Sie, dass wir für dieses Ergebnis die Floor-Funktion benötigen. Dies kann wahrscheinlich im schlimmsten Fall erreicht werden, aber die Details werden mühsam sein. Es ist nicht klar, ob die Ordnung auf den Gitterzellen auch definiert werden kann, wenn wir degradierte Gitter anstelle von Standardgittern verwenden.
Abschließend erwähnen wir eine Erweiterung der obigen Datenstruktur. Die oben beschriebene Struktur nutzt stark die Tatsache aus, dass wir nur Punkte einfügen. Es stellt sich jedoch heraus, dass die Struktur für den Umgang mit Semi-Online-Aktualisierungen, wie von Dobkin und Suri definiert, angepasst werden kann. Eine Sequenz von Aktualisierungen wird als semi-online bezeichnet, wenn die Einfügungen online erfolgen – d. h. in einer unbekannten Reihenfolge -, aber wenn ein Punkt eingefügt wird, wird uns mitgeteilt, nach wie vielen Aktualisierungen ab dem Zeitpunkt der Einfügung er gelöscht wird. Diese zusätzliche Information über die Löschungen kann verwendet werden, um zu garantieren, dass ein gelöschter Punkt immer in einem Gitter enthalten ist, das eine kleine Teilmenge speichert. Da sich bei einer Löschung der Mindestabstand vergrößern kann, speichern wir zusätzliche Informationen in der Datenstruktur, um das nächstgelegene Paar effizient zu aktualisieren. Auf diese Weise erhalten wir eine Datenstruktur der Größe O(n), die das engste Paar in O(log 2n) Worst-Case-Zeit pro Semi-Online-Aktualisierung verwaltet. Für Details verweisen wir den Leser auf Dobkin und Suri und Smid.