Quelltext der Seite Dichtestes Punktpaar

[[Datei:Closest pair of points.svg|mini|Punktmenge mit dichtestes Punktepaar in rot]]
Das Problem des '''dichtesten''' '''Punktpaares''' (''englisch'' '''closest pair of points problem''') ist die Suche nach den zwei am dichtesten beieinander liegenden [[Punkt (Geometrie)|Punkten]] in einer [[Ebene (Mathematik)|Ebene]]. Gegeben ist eine beliebige [[Menge (Mathematik)|Menge]] von Punkten in der Ebene und gesucht sind zwei dieser Punkte, sodass der [[Euklidischer Abstand|euklidische Abstand]] minimal ist. Ein ähnliches Problem ist die Suche nach den zwei am weitesten voneinander entfernten Punkten in der Ebene, also den zwei Punkten mit dem maximalen [[Euklidischer Abstand|euklidischen Abstand]].

== Kleinster Abstand von Punkten in der Ebene ==

=== Brute-force-Algorithmus ===
Der [[Brute Force|Brute-force]]-Algorithmus berechnet die [[Abstand|Abstände]] zwischen allen möglichen Punktpaaren und wählt das Punktpaar mit dem kleinsten Abstand aus. Wenn <math>n</math> die Anzahl der Punkte ist, gibt es <math>\tbinom{n}{2} = \tfrac{n \cdot (n - 1)}{2} = \tfrac{1}{2} \cdot (n^2 - n)</math> mögliche Punktpaare, für die die [[Abstand|Abstände]] berechnet werden müssen. Die [[Laufzeit (Informatik)|Laufzeit]] des [[Algorithmus]] ist also quadratisch und liegt in  <math>O(n^2)</math>.

=== Divide-and-conquer-Algorithmus ===
{{Siehe auch|Teile und herrsche (Informatik)}}
Zunächst wird die gegebene [[Menge (Mathematik)|Menge]] der Punkte einmal nach x-[[Koordinatensystem|Koordinaten]] und einmal nach y-Koordinaten [[Sortierverfahren|sortiert]]. Man erhält zwei sortierte [[Liste (Datenstruktur)|Listen]] <math>L_x</math> und <math>L_y</math>.

Der '''Divide-Schritt''' teilt die nach x-[[Koordinatensystem|Koordinaten]] sortierte [[Liste (Datenstruktur)|Liste]] <math>L_x</math> in zwei Hälften <math>P_L</math> und <math>P_R</math> links und rechts des [[Median]]s auf.

Der '''rekursive Aufruf''' geschieht nun jeweils für die beiden Hälften. Man erhält das jeweils dichteste Punktpaar beider Hälften, ohne dass eventuelle Punktpaare zwischen beiden Hälften berücksichtigt werden.

Der '''Conquer-Schritt''' kombiniert nun diese beiden Hälften. Es wird das Punktpaar mit dem kleinsten gefundenen [[Abstand]] ausgewählt. Hierbei sind zwei Fälle zu beachten:
#Das Punktpaar liegt in der linken oder der rechten Hälfte. In diesem Fall gibt es keine weiteren Probleme.
#Es gibt zwei Punkte in unterschiedlichen Hälften, deren [[Abstand]] kleiner ist, als der bisher in den Hälften gefundene. Dieser Fall ist nun gesondert zu berücksichtigen.<br /> [[Datei:Punkteinfuegen d and c.jpg|mini|hochkant|Prüfung der Nachbarn von P]]
Es ist nicht nötig, alle solchen Punktpaare einzeln durchzuprüfen. Ist <math>\delta</math> der kleinste gefundene [[Abstand]] in einer der beiden Hälften, dann ist dies eine [[obere Grenze]] für den kleinsten Abstand. Daher müssen nur noch Punkte betrachtet werden, deren Abstand zum [[Median]] in x-Richtung höchstens <math>\delta</math> beträgt. Außerdem müssen für diese Punkte nur noch Partner betrachtet werden, deren Abstand in y-Richtung kleiner als <math>\delta</math> ist.<br />Daraus ergibt sich für jeden dieser Punkte, dass lediglich der Abstand zu einer konstanten Anzahl von anderen Punkten zu prüfen ist: Denkt man sich ein [[Gitter (Geometrie)|Gitter]] der Weite <math>\tfrac{\delta}{2}</math> in der Umgebung des Medians, dann kann in jeder Gitterzelle nur einer dieser Punkte liegen, weil sonst bereits ein Abstand kleiner als <math>\delta</math> gefunden worden wäre. Weil nur diejenigen Gitterzellen zu prüfen sind, die von P aus höchstens Abstand <math>\delta</math> haben, sind maximal 24 weitere Abstände für jeden Punkt zu berechnen, nämlich jeweils maximal 12 Abstände nach oben und nach unten, womit statt quadratischer Laufzeit nur noch lineare [[Laufzeit (Informatik)|Laufzeit]] notwendig ist. Insgesamt ergibt sich für die Anzahl der berechneten Abstände die [[Rekursionsgleichung]] <math> T(n) = 2 \cdot T(\tfrac{n}{2}) + 24 \cdot n </math>, sodass die [[Laufzeit (Informatik)|Laufzeit]] in <math> O(n \cdot \log n) </math> liegt.

=== Randomisierter Algorithmus ===
==== Funktionsweise ====
Der randomisierte [[Algorithmus]] beruht darauf, dass die Punkte in zufälliger Reihenfolge in eine [[Hashtabelle]] eingefügt werden, wobei das Einfügen eines Punktes ebenso wie das Testen, ob er den vorher bekannten minimalen [[Abstand]] <math>\delta</math> unterbietet, konstante [[Laufzeit (Informatik)|Laufzeit]] hat. Die Hashtabelle bildet alle Gitterzellen der Größe <math>\left(\tfrac{\delta}{2}\right)^2</math> auf den eventuell darin liegenden Punkt ab. Es muss zwar bei jeder solchen Aktualisierung von <math>\delta</math> die Hashtabelle neu aufgebaut werden, die Gesamtzahl der Einfügeoperationen in sämtliche dieser Hashtabellen liegt aber trotzdem in <math>O(n)</math>.<br />Ohne Beachtung, wie die Hashtabelle konkret genutzt wird, ergibt sich folgender Algorithmus:

 Bilde eine zufällige Reihenfolge der Punkte P<sub>1</sub>, ..., P<sub>n</sub>
 δ = Abstand zwischen P<sub>1</sub> und P<sub>2</sub>
 Füge P<sub>1</sub> und P<sub>2</sub> in die Hashtabelle ein (Gittergröße δ/2)
 Für i = 3, ..., n
     Falls P<sub>i</sub> einen Abstand δ < δ' zu einem der Punkte P<sub>1</sub>, ..., P<sub>i-1</sub> hat:
         δ = δ'
         Baue die Hashtabelle neu auf (Gittergröße δ'/2)
     Füge P<sub>i</sub> in die Hashtabelle ein

==== Gitterstruktur und Hashfunktion ====
Man kann vereinfachend annehmen, dass alle Punkte [[Koordinatensystem|Koordinaten]] zwischen (0,0) und (1,1) haben. Gegebenenfalls kann hierfür eine [[Koordinatentransformation]] vorgenommen werden. Die Ebene, in der die Punkte liegen, wird sodann durch ein [[Gitter (Geometrie)|Gitter]] der Weite <math>\tfrac{\delta}{2}</math> überdeckt. Es wird nun eine [[universelle Hashfunktion]] benötigt; sie ermöglicht es einerseits, von einer gegebenen Gitterzelle in konstanter [[Laufzeit (Informatik)|Laufzeit]] festzustellen, ob sich in dieser Gitterzelle einer der Punkte befindet, und andererseits neue Punkte in konstanter [[Laufzeit (Informatik)|Laufzeit]] in die bestehende [[Hashtabelle]] einzufügen.

==== Einfügen neuer Punkte ====
[[Datei:Engstes punktpaar  pkt einfuegen.jpg|mini|hochkant|Einfügen von P]]
Bei jedem Einfügen eines neuen Punktes P ist zu prüfen, ob dadurch der bereits bekannte minimale [[Abstand]] <math>\delta</math> unterschritten wird. Anhand der [[Koordinatensystem|Koordinaten]] von P lässt sich sofort bestimmen, in welcher der [[Gitter (Geometrie)|Gitterzellen]] der Punkt P liegt. Aufgrund der Aufteilung in Gitterzellen der Größe <math>\left(\tfrac{\delta}{2}\right)^2</math> muss nur festgestellt werden, ob in einer der umliegenden Gitterzellen schon ein Punkt liegt. Umliegend sind dabei alle Gitterzellen, die einen solchen Abstand begründen könnten, also nur das umgebende 5x5-Rechteck. Alle Punkte, die außerhalb dieses Bereichs liegen, können keinen kleineren Abstand zu P haben, weil sie aufgrund der Gittergröße mindestens den Abstand <math>2 \cdot \tfrac{\delta}{2} = \delta</math> haben. Weil in jeder Gitterzelle nur ein einziger Punkt liegen kann, denn sonst wäre vorher bereits ein kleinerer Abstand gefunden worden, müssen also auch nur höchstens 25 Punkte geprüft werden. Sofern in diesem Bereich keine Punkte liegen, kann P bedenkenlos in die bestehende [[Hashtabelle]] eingefügt werden.

Sind jedoch in diesem Bereich bereits weitere Punkte vorhanden, so wird der Abstand <math>\delta</math> auf den neu gefundenen minimalen Abstand gesetzt. Dies hat zur Folge, dass die bisherige [[Hashtabelle]] nutzlos geworden ist, weil ihre Gitterweite nicht mehr mit <math>\tfrac{\delta}{2}</math> übereinstimmt. Wir benötigen also eine neue Hashtabelle mit korrektem <math>\delta</math>. Wir erstellen einfach eine solche Tabelle für alle Punkte bis zu P von Grund auf neu. Der Effizienz halber kann man sich beim Neuerstellen die Abstandsprüfung sparen, weil der minimale Abstand aller Punkte zu P bereits bekannt ist.

Schließlich hat man nach dem Einfügen eines neuen Punktes immer eine korrekte [[Hashtabelle]] mit Gitterweite <math>\tfrac{\delta}{2}</math> und in jedem Gitterquadrat liegt höchstens ein Punkt.

==== Laufzeit ====
Relevant für die [[Laufzeit (Informatik)|Laufzeit]] ist lediglich die Anzahl der Einfüge-[[Operation (Informatik)|Operationen]] neuer Punkte. Trivialerweise muss jeder Punkt mindestens einmal eingefügt werden, also ist die Laufzeit mindestens linear.

Fraglich ist jedoch, wie sich der gelegentlich vorkommende Neuaufbau der [[Hashtabelle]] auswirkt, weil hierfür alle bereits bekannten Punkte erneut eingefügt werden müssen. Hierfür ist es notwendig, die [[Wahrscheinlichkeit]] anzugeben, mit der beim Einfügen eines Punkts ein Neuaufbau erforderlich wird, und die dafür notwendigen Kosten einzuberechnen. Intuitiv sieht man, dass mit zunehmender Anzahl der Punkte der Aufwand für die Reorganisation immer größer wird, die Wahrscheinlichkeit dafür aber immer kleiner.

Der [[Erwartungswert]] für die [[Laufzeit (Informatik)|Laufzeit]] kann wie folgt berechnet werden:

Die [[Wahrscheinlichkeit]] dafür, dass der Punkt <math>P_i</math> beim Einfügen einen kleineren [[Abstand]] erzeugt, ist gleich <math>\tfrac{2}{i}</math>, denn dafür müsste <math>P_i</math> einer der 2 Punkte sein, die diesen Abstand zueinander haben.

Definieren wir nun die [[Zufallsvariable]] <math>X_i \longrightarrow \{0, 1\}</math>. Sie sei 1, falls beim Einfügen des Punkts <math>P_i</math> ein kleinerer Abstand entsteht, und sonst 0.

Dann gilt: Die Gesamtanzahl der Einfügeoperationen ist <math>n + \sum^n_{i=2} i \cdot X_i</math>, also die Anzahl <math>n</math> der eingefügten Punkte plus die Anzahl der Einfügeoperationen durch die Neuorganisationen der [[Hashtabelle]].

Für den [[Erwartungswert]] gilt aufgrund dessen [[Erwartungswert#Linearität|Linearität]]: <math>E(X) = n + \sum^n_{i=2} i \cdot E(X_i) = n + \sum^n_{i=2} i \cdot \tfrac{2}{i} = n + 2 \cdot (n - 1) = 3 \cdot n - 2
</math>.

Das heißt, die Gesamtanzahl der erwarteten Einfügeoperationen ist lediglich gleich <math>3 \cdot n - 2</math>. Insgesamt ist die erwartete [[Laufzeit (Informatik)|Laufzeit]] somit linear, liegt also in <math>O(n)</math>.

== Größter Abstand von Punkten in der Ebene ==

=== Rotating calipers Algorithmus ===
Der Rotating calipers Algorithmus ist danach benannt, dass ein [[Messschieber]] um die Außenseite eines [[Konvexes Polygon|konvexen Polygons]] gedreht wird. Jedes Mal, wenn ein Messschenkel flach an einer Seite des [[Polygon]]s liegt, bildet es ein antipodales Punktpaar, wobei der Punkt oder die Seite den entgegengesetzte Messschenkel berührt. Die vollständige [[Drehung]] des Messschiebers um das Polygon erkennt alle antipodalen Punktpaare und bestimmt das Punktepaar mit dem größten [[Abstand]].

Um den [[Algorithmus]] auf beliebige Punkte in der Ebene anwenden zu können, muss erst die [[konvexe Hülle]] der Punkte bestimmt werden. Dafür wird die [[Laufzeit (Informatik)|Laufzeit]] <math> O(n \cdot \log n) </math> benötigt.

Zwei Punkte mit maximalem [[Abstand]] müssen auf den Rand des [[Konvexes Polygon|konvexen Polygons]] liegen, das die [[konvexe Hülle]] bildet. Der [[Algorithmus]] beginnt mit den Punkten <math>P_n</math> und <math>P_1</math> und berechnet den [[Flächeninhalt]] der Dreiecke <math>P_nP_1P_k</math>. Zunächst wird <math>k = 2</math> gesetzt und so lange erhöht, wie der Flächeninhalt zunimmt. So wird der antipodalen Punkt für <math>P_1</math> bestimmt. Auf ähnliche Weise wird der antipodale Punkt für <math>P_2</math> bestimmt wird, indem der Flächeninhalt der Dreiecke <math>P_1P_2P_k</math> berechnet wird und der Index <math>k</math> weiter erhöht wird, so lange der Flächeninhalt zunimmt. Diese Schritte werden mit den anderen Punkten <math>P_i</math> wiederholt, bis der Index <math>k</math> erreicht ist, also <math>i = k</math> ist. Die Abstände der antipodalen Punktpaare werden berechnet und mit dem größten bisher gefundenen Abstand verglichen. Die [[Laufzeit (Informatik)|Laufzeit]] für die Berechnung der Flächeninhalte und Abstände liegt in <math> O(n) </math>.

Insgesamt ergibt sich die [[Laufzeit (Informatik)|Laufzeit]] <math> O(n \cdot \log n) + O(n) = O(n \cdot \log n) </math>.

== Literatur ==
* Thomas H. Cormen, [[Charles E. Leiserson]], [[Ronald L. Rivest]] und Clifford Stein: ''Algorithmen – Eine Einführung''. Oldenbourg-Verlag, 2004. ISBN 3-486-27515-1, Kapitel 33.4: Berechnung des dichtesten Punktepaares, S. 959–963.
* [[Jon Kleinberg]], [[Éva Tardos]]. ''Algorithm Design''. Pearson International Edition, 2006. ISBN 0-321-37291-3. Seiten 225 ff (Divide & Conquer); S. 741 ff (Randomisierter Algorithmus).

[[Kategorie:Suchalgorithmus]]