Dichtestes Punktpaar

Das Problem des dichtesten Punktpaares (englisch closest pair of points problem) ist die Suche nach den zwei am dichtesten beieinander liegenden Punkten in einer Ebene. Gegeben ist eine beliebige Menge von Punkten in der Ebene und gesucht sind zwei dieser Punkte, sodass der 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 euklidischen Abstand.

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

Zunächst wird die gegebene Menge der Punkte einmal nach x-Koordinaten und einmal nach y-Koordinaten sortiert. Man erhält zwei sortierte Listen ${\displaystyle L_{x}}$ und ${\displaystyle L_{y}}$.

Der Divide-Schritt teilt die nach x-Koordinaten sortierte Liste ${\displaystyle L_{x}}$ in zwei Hälften ${\displaystyle P_{L}}$ und ${\displaystyle P_{R}}$ links und rechts des Medians 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:

1. Das Punktpaar liegt in der linken oder der rechten Hälfte. In diesem Fall gibt es keine weiteren Probleme.
2. 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.
   

Es ist nicht nötig, alle solchen Punktpaare einzeln durchzuprüfen. Ist ${\displaystyle \delta }$ 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 ${\displaystyle \delta }$ beträgt. Außerdem müssen für diese Punkte nur noch Partner betrachtet werden, deren Abstand in y-Richtung kleiner als ${\displaystyle \delta }$ ist.
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 der Weite ${\displaystyle {\tfrac {\delta }{2}}}$ in der Umgebung des Medians, dann kann in jeder Gitterzelle nur einer dieser Punkte liegen, weil sonst bereits ein Abstand kleiner als ${\displaystyle \delta }$ gefunden worden wäre. Weil nur diejenigen Gitterzellen zu prüfen sind, die von P aus höchstens Abstand ${\displaystyle \delta }$ 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 notwendig ist. Insgesamt ergibt sich für die Anzahl der berechneten Abstände die Rekursionsgleichung ${\displaystyle T(n)=2\cdot T({\tfrac {n}{2}})+24\cdot n}$, sodass die Laufzeit in ${\displaystyle O(n\cdot \log n)}$ liegt.

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 ${\displaystyle \delta }$ unterbietet, konstante Laufzeit hat. Die Hashtabelle bildet alle Gitterzellen der Größe ${\displaystyle \left({\tfrac {\delta }{2}}\right)^{2}}$ auf den eventuell darin liegenden Punkt ab. Es muss zwar bei jeder solchen Aktualisierung von ${\displaystyle \delta }$ die Hashtabelle neu aufgebaut werden, die Gesamtzahl der Einfügeoperationen in sämtliche dieser Hashtabellen liegt aber trotzdem in ${\displaystyle O(n)}$.
Ohne Beachtung, wie die Hashtabelle konkret genutzt wird, ergibt sich folgender Algorithmus:

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

Man kann vereinfachend annehmen, dass alle Punkte 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 der Weite ${\displaystyle {\tfrac {\delta }{2}}}$ überdeckt. Es wird nun eine universelle Hashfunktion benötigt; sie ermöglicht es einerseits, von einer gegebenen Gitterzelle in konstanter Laufzeit festzustellen, ob sich in dieser Gitterzelle einer der Punkte befindet, und andererseits neue Punkte in konstanter Laufzeit in die bestehende Hashtabelle einzufügen.

Bei jedem Einfügen eines neuen Punktes P ist zu prüfen, ob dadurch der bereits bekannte minimale Abstand ${\displaystyle \delta }$ unterschritten wird. Anhand der Koordinaten von P lässt sich sofort bestimmen, in welcher der Gitterzellen der Punkt P liegt. Aufgrund der Aufteilung in Gitterzellen der Größe ${\displaystyle \left({\tfrac {\delta }{2}}\right)^{2}}$ 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 ${\displaystyle 2\cdot {\tfrac {\delta }{2}}=\delta }$ 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 ${\displaystyle \delta }$ auf den neu gefundenen minimalen Abstand gesetzt. Dies hat zur Folge, dass die bisherige Hashtabelle nutzlos geworden ist, weil ihre Gitterweite nicht mehr mit ${\displaystyle {\tfrac {\delta }{2}}}$ übereinstimmt. Wir benötigen also eine neue Hashtabelle mit korrektem ${\displaystyle \delta }$. 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 ${\displaystyle {\tfrac {\delta }{2}}}$ und in jedem Gitterquadrat liegt höchstens ein Punkt.

Relevant für die Laufzeit ist lediglich die Anzahl der Einfüge-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 kann wie folgt berechnet werden:

Die Wahrscheinlichkeit dafür, dass der Punkt ${\displaystyle P_{i}}$ beim Einfügen einen kleineren Abstand erzeugt, ist gleich ${\displaystyle {\tfrac {2}{i}}}$, denn dafür müsste ${\displaystyle P_{i}}$ einer der 2 Punkte sein, die diesen Abstand zueinander haben.

Definieren wir nun die Zufallsvariable ${\displaystyle X_{i}\longrightarrow \{0,1\}}$. Sie sei 1, falls beim Einfügen des Punkts ${\displaystyle P_{i}}$ ein kleinerer Abstand entsteht, und sonst 0.

Dann gilt: Die Gesamtanzahl der Einfügeoperationen ist ${\displaystyle n+\sum _{i=2}^{n}i\cdot X_{i}}$, also die Anzahl ${\displaystyle n}$ der eingefügten Punkte plus die Anzahl der Einfügeoperationen durch die Neuorganisationen der Hashtabelle.

Für den Erwartungswert gilt aufgrund dessen Linearität: ${\displaystyle E(X)=n+\sum _{i=2}^{n}i\cdot E(X_{i})=n+\sum _{i=2}^{n}i\cdot {\tfrac {2}{i}}=n+2\cdot (n-1)=3\cdot n-2}$.

Das heißt, die Gesamtanzahl der erwarteten Einfügeoperationen ist lediglich gleich ${\displaystyle 3\cdot n-2}$. Insgesamt ist die erwartete Laufzeit somit linear, liegt also in ${\displaystyle O(n)}$.

Der Rotating calipers Algorithmus ist danach benannt, dass ein Messschieber um die Außenseite eines konvexen Polygons gedreht wird. Jedes Mal, wenn ein Messschenkel flach an einer Seite des Polygons 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 ${\displaystyle O(n\cdot \log n)}$ benötigt.

Zwei Punkte mit maximalem Abstand müssen auf den Rand des konvexen Polygons liegen, das die konvexe Hülle bildet. Der Algorithmus beginnt mit den Punkten ${\displaystyle P_{n}}$ und ${\displaystyle P_{1}}$ und berechnet den Flächeninhalt der Dreiecke ${\displaystyle P_{n}P_{1}P_{k}}$. Zunächst wird ${\displaystyle k=2}$ gesetzt und so lange erhöht, wie der Flächeninhalt zunimmt. So wird der antipodalen Punkt für ${\displaystyle P_{1}}$ bestimmt. Auf ähnliche Weise wird der antipodale Punkt für ${\displaystyle P_{2}}$ bestimmt wird, indem der Flächeninhalt der Dreiecke ${\displaystyle P_{1}P_{2}P_{k}}$ berechnet wird und der Index ${\displaystyle k}$ weiter erhöht wird, so lange der Flächeninhalt zunimmt. Diese Schritte werden mit den anderen Punkten ${\displaystyle P_{i}}$ wiederholt, bis der Index ${\displaystyle k}$ erreicht ist, also ${\displaystyle i=k}$ ist. Die Abstände der antipodalen Punktpaare werden berechnet und mit dem größten bisher gefundenen Abstand verglichen. Die Laufzeit für die Berechnung der Flächeninhalte und Abstände liegt in ${\displaystyle O(n)}$.

Insgesamt ergibt sich die Laufzeit ${\displaystyle O(n\cdot \log n)+O(n)=O(n\cdot \log n)}$.

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