Dichtestes Punktpaar

Aufgabe und Grundidee

Beim Problem des dichtesten Punktpaares wird in einer beliebigen Menge von Punkten der Ebene ein Paar gesucht, dessen euklidischer Abstand minimal ist. Es ist ein grundlegendes geometrisches Suchproblem: Statt alle möglichen Abstände unnötig oft zu prüfen, nutzen schnellere Verfahren die räumliche Lage der Punkte.

Das verwandte Problem des größten Punktabstands sucht dagegen zwei Punkte mit maximalem euklidischen Abstand.

Kleinster Abstand: vollständige und geteilte Suche

Der Brute-force-Algorithmus berechnet den Abstand jedes möglichen Punktpaars und wählt den kleinsten. Für n Punkte gibt es genau (n über 2) = n·(n−1)/2 = 1/2·(n²−n) Paare. Daher beträgt seine Laufzeit O(n²).

Der Divide-and-conquer-Algorithmus ist schneller. Zuerst werden die Punkte einmal nach der x-Koordinate und einmal nach der y-Koordinate sortiert; die Listen heißen Lₓ und Lᵧ. Lₓ wird am Median in eine linke Hälfte Pₗ und eine rechte Hälfte Pᵣ geteilt. Rekursiv wird für beide Hälften jeweils das dichteste Paar bestimmt.

Danach muss geprüft werden, ob das gesuchte Paar einen Punkt aus jeder Hälfte enthält. Sei δ der kleinste Abstand, der bisher innerhalb einer Hälfte gefunden wurde. Betrachtet werden nur Punkte, deren x-Abstand zum Median höchstens δ ist; als mögliche Partner kommen nur Punkte mit y-Abstand kleiner als δ infrage. Mit einem Gitter der Weite δ/2 kann in jeder Gitterzelle höchstens ein Punkt liegen, da sonst bereits ein Abstand kleiner als δ vorläge. Für jeden Punkt sind höchstens 24 weitere Abstände zu prüfen, höchstens 12 nach oben und 12 nach unten. Der Zusammenführungsschritt ist damit linear. Die Rekursionsgleichung lautet T(n) = 2·T(n/2) + 24·n, insgesamt ist die Laufzeit O(n·log n).

Randomisierte Suche mit Gitter und Hashtabelle

Beim randomisierten Algorithmus werden die Punkte P₁, …, Pₙ in zufälliger Reihenfolge verarbeitet. δ ist der bisher bekannte minimale Abstand. Eine Hashtabelle ordnet Gitterzellen der Größe (δ/2)² jeweils einem möglichen darin liegenden Punkt zu. Das Nachschlagen und Einfügen in die Hashtabelle erfolgt in konstanter Laufzeit.

Zu Beginn wird δ als Abstand von P₁ und P₂ gesetzt; beide Punkte werden eingefügt. Für jeden weiteren Punkt Pᵢ wird geprüft, ob sein Abstand zu einem bereits eingefügten Punkt kleiner als δ ist. Falls ein neuer kleinerer Abstand δ′ gefunden wird, setzt man δ = δ′, baut die Hashtabelle mit der neuen Gitterweite δ′/2 neu auf und fügt Pᵢ ein. Andernfalls wird Pᵢ direkt eingefügt.

Für die Gitterbeschreibung dürfen die Koordinaten vereinfachend durch eine Koordinatentransformation in den Bereich von (0,0) bis (1,1) gebracht werden. Beim Einfügen eines Punkts muss nur das umgebende 5×5-Rechteck aus Gitterzellen geprüft werden. Punkte außerhalb dieses Bereichs haben wegen der Gittergröße mindestens den Abstand 2·δ/2 = δ. Da pro Zelle höchstens ein Punkt liegen kann, werden höchstens 25 Punkte geprüft. Nach jedem Einfügen enthält die Tabelle somit höchstens einen Punkt je Gitterquadrat und besitzt die passende Gitterweite δ/2.

Ein Neuaufbau kann zwar viele erneute Einfügungen benötigen, wird aber mit wachsender Punktzahl seltener. Die Wahrscheinlichkeit, dass Pᵢ beim Einfügen einen kleineren Abstand erzeugt, beträgt 2/i: Pᵢ müsste einer der zwei Punkte des dann dichtesten Paars sein. Mit der Zufallsvariable Xᵢ ∈ {0,1}, die bei einem Neuaufbau 1 ist, lautet die Zahl aller Einfügeoperationen n + Σᵢ₌₂ⁿ i·Xᵢ. Ihr Erwartungswert ist E(X) = n + Σᵢ₌₂ⁿ i·E(Xᵢ) = n + Σᵢ₌₂ⁿ i·2/i = n + 2·(n−1) = 3·n−2. Die erwartete Laufzeit ist daher O(n).

Größter Abstand und rotierende Messschieber

Für den größten Abstand wird der Rotating-calipers-Algorithmus verwendet. Er stellt bildlich einen Messschieber dar, der um die Außenseite eines konvexen Polygons gedreht wird. Liegt ein Messschenkel an einer Polygonseite an, bilden die berührten gegenüberliegenden Punkte oder Seiten ein antipodales Punktpaar. Während einer vollständigen Drehung werden alle solchen Paare untersucht; daraus wird das Paar mit dem größten Abstand bestimmt.

Bei einer beliebigen Punktmenge wird zuerst ihre konvexe Hülle berechnet, also das kleinste konvexe Polygon, das alle Punkte umfasst. Dies benötigt O(n·log n). Ein Paar mit maximalem Abstand liegt auf dem Rand dieses Polygons.

Der Algorithmus beginnt mit Pₙ und P₁. Für Dreiecke PₙP₁Pₖ wird der Flächeninhalt berechnet, wobei k bei 2 beginnt und erhöht wird, solange der Flächeninhalt wächst. So wird der antipodale Punkt zu P₁ gefunden. Für P₂ wird entsprechend mit den Dreiecken P₁P₂Pₖ verfahren; dies wird für weitere Pᵢ wiederholt, bis i = k ist. Die Abstände der antipodalen Paare werden jeweils mit dem bisher größten Abstand verglichen. Die Berechnung von Flächeninhalten und Abständen benötigt O(n), zusammen mit der konvexen Hülle also O(n·log n) + O(n) = O(n·log n).