Das Closest-Pairs Problem. Wer ist wem am nahesten?


Ausarbeitung, 2016

8 Seiten, Note: 1,3


Leseprobe


Inhaltsverzeichnis

1 Motivation .. 2

2 Grundlagen .. 2

2.1 Euklidischer Abstand .. 2

2.2 Engstes eindimensionales Punktpaar .. 2

2.3 Naiver Algorithmus .. 2

2.3.1 Implementierung .. 3

2.4 Eindimensionaler Divide and Conquer Algorithmus .. 3

2.4.1 Implementierung .. 4

3 Closest-Pairs Algorithmus .. 4

3.1 Divide and Conquer .. 4

3.1.1 Teile .. 4

3.1.2 Hersche .. 5

3.1.3 Kombiniere .. 5

3.2 Pseudocode .. 6

4 Beweis .. 7

4.1 Korrektheit .. 7

4.2 Laufzeit .. 7

5 Ausblick .. 8

5.1 Laufzeitverbesserung durch Randomisierung .. 8

6 Quellen .. 8

1 Motivation

Wenn eine Ebene mit n größer gleich 2 Punkten gegeben ist möchte man sicherlich nach dem am nahesten beieinander liegenden Punktpaar suchen. Es handelt sich dabei um das Closest-Pairs Problem aus der Geometrie, welches Anwendung in geographischen Informationssystemen, wie beispielsweise Verkehrsleitsystemen, sowie Computergrafik, Computer Vision und im Molekulardesign findet. Auch wenn es sich um eines der natürlichsten geographischen Probleme handelt, ist es schwierig einen effizienten Algorithmus zu finden. Auf den folgenden Seiten werden wir uns somit langsam an einen schnellen O(n log n) Algorithmus antasten und am Ende noch einen Ausblick für eine O(n) Lösung geben.

2 Grundlagen

Im Folgenden betrachten wir eine Menge aus Punkten P = {p1 … p n} wobei pi

[Formel ist nicht enthalten in dieser Leseprobe]

R x R die kartesischen Koordinaten (xi; yi) besitzt und P mindestens aus 2 Punkten besteht. Das Ziel ist es ein Punktpaar (pi; p j) mit

[Formel ist nicht enthalten in dieser Leseprobe]

zu finden, wo der euklidischen Abstand zwischen den Punkten minimal ist.

2.1 Euklidischer Abstand

Die Länge zwischen zwei Punkten p1 = (x1; y 1) und p 2 = (x2; y2) heißt Euklidischer Abstand und wird durch d(p1; p2) gekennzeichnet. Mit Hilfe des Pythagoras errechnet sich der Euklidische Abstand in einer zweidimensionalen Ebene dann wie folgt: [1]

[Formel ist nicht enthalten in dieser Leseprobe]

2.2 Engstes eindimensionales Punktpaar

Gegeben seien die Punkte pi = (xi; y) mit einer festen y-Koordinate, die sich in einem Eindimensionalen Raum befinden. Um das dichteste Punktpaar finden zu können, müssen die Punkte zunächst in O( n log n) sortiert werden. Ein Punkt im eindimensionalen Raum kann nur höchstens zwei Nachbarn haben, somit muss die sortierte Liste nun nur einmal durchgelaufen werden um die Distanz zwischen den benachbarten Punkten zu errechnen. Ein Punktpaar muss folglich die kleinste Distanz haben.

2.3 Naiver Algorithmus

Ein naiver Algorithmus kann das dichteste Punktpaar im zweidimensionalen Raum in O(n2) berechnen. Er betrachtet alle Distanzen zwischen allen Punktpaaren, die in dem Raum möglich sind und findet so den minimalsten Abstand. Um zu einem Ergebnis zu kommen benötigt er also

[Formel ist nicht enthalten in dieser Leseprobe]

Vergleiche.

2.3.1 Implementierung

[Abb. ist nicht enthalten in dieser Leseprobe]

Listing 1: Naive Brute-Force Methode (Pseudocode)

2.4 Eindimensionaler Divide and Conquer Algorithmus

In höheren Dimensionen wird eine Teile und Hersche Methode verwendet. Um diese zu verstehen betrachten wir die Methode zunächst im Eindimensionalen. Gegeben seien wiederum Punkte pi = (xi; y) mit einer fester y-Koordinate die sich in einem Eindimensionalen Raum befinden. Wir erinnern uns, um das dichteste Punktpaar zu finden, mussten die Punkte in einer sortierten Liste mit ihren Nachbarn verglichen werden. Dies verallgemeinert jedoch nicht das Finden dichtester Punktpaare in höheren Dimensionen [2]; da es in höheren Dimensionen keine direkten Nachbarn gibt. In höheren Dimensionen müssen wir das Problem zuerst in kleinere Teilprobleme aufteilen.

Teile: Wir nehmen uns die bereits Sortierte Liste S und teilen diese in der Mitte m, sodass zwei Hälften S L und SR entsteht.

[Formeln sind nicht enthalten in dieser Leseprobe]

Die dabei entstandenen Unterlisten teilen wir wiederum rekursiv in weitere Listen auf, bis nur noch n kleiner gleich 2 Elemente in den Listen vorhanden sind.

Hersche: [Formel sind nicht enthalten in dieser Leseprobe]

Kombiniere: Nun kann es sein, dass der dichteste Abstand entweder durch die rekursiven Aufrufe entstandene A (Zeichen kann nicht angezeigt werden und wird im weiteren Verlauf als A bezeichnet) ist, oder zwischen m in SL und SR liegt. Im eindimensionalen Raum ist ein Element li immer das am weitesten rechte Element und r i immer das am weitesten linke Element, was für größere Dimensionen nicht gilt. Somit ist es leicht rekursiv das dichteste Punktpaar zu finden

[Formel ist nicht enthalten in dieser Leseprobe]

2.4.1 Implementierung

[Abb. ist nicht enthalten in dieser Leseprobe]

Listing 2: 1D Divide and Conquer (Pseudocode)

3 Closest-Pairs Algorithmus

3.1 Divide and Conquer

Der Closest Pair of Points Algorithmus folgt dem Teile-und-Herrsche Prinzip, indem das Problem rekursiv in kleinere Teilprobleme zerlegt wird, bis man diese mit geringem Aufwand lösen kann. Aus diesen Teillösungen wird dann eine Lösung für das Gesamtproblem rekonstruiert. Insgesamt soll der Aufwand zum Lösen eines solchen Problems O(n log n) sein.

3.1.1 Teile

Wir machen uns bewusst, dass vor dem rekursiven Aufruf mit P eine Menge von Punkten gegeben ist, dabei soll P mindestens zwei Punkte beinhalten. Zum besseren Verständnis des Algorithmus nehmen wir an, dass es keine zwei Punkte in P gibt, die die gleiche x- oder y-Koordinate haben. Folglich werden durch das Erstellen der Listen Px und Py alle Punkte aus P nach ihren x- und y-Koordinaten sortiert. Zu jedem Eintrag wird die Position der Punkte in beiden Listen gespeichert. Der erste rekursive Schritt (alle weiteren analog) sieht so aus, dass wir mit Q eine Menge von Punkten definieren, die aus den Positionen der Liste P x (die erste Hälfte) stammen und mit R eine Menge von Punkten definieren, die aus den letzten Positionen der Liste Px (die zweite Hälfte) stammen. In einem einzigen Durchlauf durch die Listen P x und Py in O(n) Zeit können wir die folgenden vier Listen erstellen: Qx beinhaltet die Punkte aus Q, sortiert nach steigenden x-Koordinaten; Qy beinhaltet die Punkte aus Q, sortiert nach steigenden y-Koordinaten; und analog gilt das für die Listen Rx und Ry mit R. Für jeden Eintrag wird wieder die Position der Punkte in beiden Listen gespeichert. Die Rekursion hört auf, wenn Pi drei Elemente oder weniger hat.

3.1.2 Hersche

Wenn die Rekursion aufhört und Pn drei Elemente oder weniger hat, werden alle Abstände zwischen diesen Punkten mit Hilfe des euklidischen Abstands berechnet. Der kleinste Abstand wird für das Kombinieren gespeichert.

3.1.3 Kombiniere

Von P aus betrachtet haben wir bisher jeweils nur den minimalen Abstand von zwei Punkten in Q mit

[Formeln sind nicht enthalten in dieser Leseprobe]

Weiterhin sei A definiert als = min(A1; A2). Wir beschäftigen uns im Folgenden damit, herauszufinden, ob es einen Punkt gibt, für das gilt

[Formel ist nicht enthalten in dieser Leseprobe] .

Ist das nicht der Fall so ist mit A der minimale Abstand von zwei Punkten in P gegeben, andernfalls müssen wir

[Formel ist in dieser Leseprobe nicht enthalten]

herausfinden. Sei x* die x-Koordinate des Punktes in Q, das den größten x-Wert hat (bzw. am weitesten rechts steht) und L sei die vertikale Linie, die mit der Gleichung x = x* beschrieben wird. Diese Linie L trennt Q von R. Dann gilt dieser Satz: [3]

[Formel ist nicht enthalten in dieser Leseprobe]

Beweis:

[Formel sind nicht enthalten in dieser Leseprobe]

Beim Auffinden solcher q's und r's können wir uns dann auf die Punkte in P beschränken, die weit zur Linie L entfernt sind. Sei

[Formel ist nicht enthalten in dieser Leseprobe]

die Menge, die genau diese Punkte als Elemente hat und Sy die Liste, die diese Punkte nach aufsteigender y-Koordinate sortiert enthält. In einem Durchlauf durch Py ist Sy in O(n) Zeit konstruiert. An diesem Punkt ist anzumerken, dass S die ganze Menge P sein könnte. In diesem Fall würde uns 4.8 nichts bringen. Doch das ist tatsächlich nicht der Fall, wie uns der nächste Satz zeigen wird.

[Formel ist nicht enthalten in dieser Leseprobe ]

Beweis: Betrachten wir Z als Teilmenge von S, so dass die Punkte in Z ebenfalls maximal weit von der Linie L entfernt liegen. Wir partitionieren Z in Boxen: Quadrate mit 2 vertikalen und 2 horizontalen Seitenlängen. Eine Reihe in Z soll genau aus vier solcher Kästchen bestehen. Zwei sind jeweils links von L und die anderen zwei sind rechts von L. Angenommen zwei Punkte von S liegen in derselben Box. Da alle Punkte, die in dieser Box sind, auf derselben Seite von L liegen, gehören diese beiden Punkte zu Q oder zu R. Außerdem ist der Abstand zu diesen zwei Punkten kleiner gleich

[Formel ist nicht enthalten in dieser Leseprobe]

Es ist dann aber

[Formel ist nicht enthalten in dieser Leseprobe]

was ein Widerspruch ist, denn wir hatten angenommen, dass der kleinste Abstand zweier Punkte aus Q oder R ist. Folglich hat eine solche Box höchstens einen Punkt aus S. Angenommen es gibt die Punkte s, s0 mit d(s; s0) kleiner als S und diese sind in der Liste Sy mindestens 16 Positionen voneinander entfernt. Sei OBdA s der Punkt mit der kleineren y-Koordinate. Da es in jeder Box höchstens einen Punkt geben kann, gibt es zwischen s und s' mindestens einen Abstand von drei Reihen. Für alle Punktepaare in Z, die mindestens einen Abstand von drei Reihen haben, gilt aber,

dass der Abstand mindestens

[Formel ist nicht enthalten in dieser Leseprobe]

sein muss. Das ist ein Widerspruch zu unserer Annahme, dass für s, s' d(s; s') kleiner als gelte und diese in der Liste Sy mindestens 16 Positionen voneinander entfernt sind.

Es ist anzumerken, dass der Vergleich für einen Punkt in der Liste S y mit seinen 15 Nachfolgern reduzierbar ist. Für unsere Zwecke ist mitzunehmen, dass dieser Wert eine Konstante ist.

In Betracht von Satz 4.10 können wir den Algorithmus wie folgt abschließen. Wir durchlaufen die Elemente von der Liste Sy und berechnen für jedes s ;Element; S den Abstand zu seinen 15 Nachfolgern. Satz 4.10 impliziert in diesem Fall, dass wir mindestens den Abstand von allen potenziellen Punktepaaren aus S berechnet haben, deren Abstand kleiner als S. Anschließend können wir die kleinste Distanz zweier Punkte vergleichen.

(i) Ist diese Distanz kleiner als AF , dann sind diese zwei Punkte aus S, die am nahesten zueinander liegenden Punkte in ganz P.

(ii) Ist größer als diese Distanz, dann sind die am nahesten zueinander liegenden Punkte bei unserem rekursiven Aufruf bestimmt worden. Damit haben können wir in P die am dichtesten zueinander liegenden Punkte bestimmt.

3.2 Pseudocode

[Abb. ist nicht enthalten in dieser Leseprobe]

Listing 3: Closest-Pairs Divide and Conquer (Pseudocode)

4 Beweis

4.1 Korrektheit

Satz (5.11). [3] Der Algorithmus gibt das dichteste Punktpaar in P korrekt aus.

Beweis: Zunächst stellen wir mithilfe einer Induktion sicher, dass P niemals rekursiv geteilt wird. Somit können wir sicherstellen, dass die kürzesten Punktepaare durch die Rekursion korrekt bestimmt werden. Mit Hilfe der Sätze (5.8) und (5.10) können wir korrekt feststellen, ob Q oder R beide Punkte enthält, ober ob das kürzeste Punktepaar aus einem Punkt von Q und einem Punkt aus R besteht. Folglich kann durch die Rekursion die kürzeste Distanz bestimmt werden.

4.2 Laufzeit

Satz (5.12). [3] Die Laufzeit des Algorithmus beträgt O(n log n)

Beweis: Die initiale Sortierung von Px und Py beträgt O(n log n). Man beachte nun, dass das Aufteilen von Q und R leicht in linearer Zeit vollständig ausgeführt werden kann. Die Hauptschwierigkeit ist nun sicherzustellen, dass die in den rekursiven Aufrufen übergebenen Felder Qx;Qy;Rx;Ry und das Feld Sy nach der richtigen Koordinate sortiert sind. Da bereits vorsortiert wurde, müssen nur sortierte Listen zerlegt oder zusammengefügt werden. Das Zusammenfügen von zweier Sortierter Listen kann dann mit Hilfe einer Merge Prozedur ähnlich wie beim "Merge-Sort" Verfahren erreicht werden.

Somit beträgt die Laufzeit T(n) = O(n log n) + O(n)

5 Ausblick

5.1 Laufzeitverbesserung durch Randomisierung

Die naive Methode kann jedoch noch deutlich verbessert werden. Mit Hilfe assoziativer Datenfelder und einer randomisierten Methode kann das Problem in O(n) Laufzeit plus O(n) Wörterbuchoperation gelöst werden. Wir betrachten P in zufälliger Reihenfolge und setzen = d(p1; p 2) als die kürzeste Distanz. Daraufhin betrachten wir einen weiteren Punkt pi und schauen ob die Vorherigen Punkte dichter waren. Wenn die Distanz dichter ist, müssen wir das kürzeste Paar aktualisieren. Die Herausforderung diese Methode in einen schnellen Algorithmus zu verwandeln, liegt darin wie man nach Punkten in der Nähe sucht.


[Su15] S. Suri: Closest-pair problem. CS 235: Computational Geometry, Fall '15, 2015

[1][Br16] Bronstein; Semendjajew; Musiol; Mühlig; 2016; S.198

[2 [Su15] Suri, Subhash; 2015

[3] [KT05] Kleinberg, Jon; Tardos, Eva; 2005; S.134

6 Quellen

[Br16] I. Bronstein; K. A. Semendjajew; G. Musiol; H. Mühlig: Taschenbuch der Mathematik, 2016; S.198

[Co07] Th. H. Cormen; Ch. E. Leiserson; R. Rivest; C. Stein: Algorithmen - Eine Einführung. 2. Auflage, Oldenbourg, 2007. S.959

[KT05] J. Kleinberg, E. Tardos: Algorithm Design. Pearson, 2005. S.131

[RTTA] rosettacode.org: Closest-pair problem. www.rosettacode.org/wiki/Closest-pair_problem, Abruf am 13. Juni 2016

[Su15] S. Suri: Closest-pair problem. CS 235: Computational Geometry, Fall '15, 2015

Ende der Leseprobe aus 8 Seiten

Details

Titel
Das Closest-Pairs Problem. Wer ist wem am nahesten?
Hochschule
Universität Hamburg
Veranstaltung
Proseminar - Algorithmik
Note
1,3
Autoren
Jahr
2016
Seiten
8
Katalognummer
V350017
ISBN (eBook)
9783668374560
ISBN (Buch)
9783668374577
Dateigröße
563 KB
Sprache
Deutsch
Schlagworte
closest-pairs, problem
Arbeit zitieren
Tim Kilian (Autor:in)Deniz Guel (Autor:in), 2016, Das Closest-Pairs Problem. Wer ist wem am nahesten?, München, GRIN Verlag, https://www.grin.com/document/350017

Kommentare

  • Noch keine Kommentare.
Blick ins Buch
Titel: Das Closest-Pairs Problem. Wer ist wem am nahesten?



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden