In folgender Ausarbeitung wird ein effizienter Divide & Conquer-Algorithmus zur Bestimmung desjenigen Punktepaares, welches unter einer Menge von Punkten den geringsten Abstand zueinander aufweist, vorgestellt.
Kurzfassung
In folgender Ausarbeitung wird ein effizienter
”Divide&Conquer“-AlgorithmuszurBestimmungdes- jenigen Punktepaares, welches unter einer Menge von Punkten den geringsten Abstand zueinander aufweist, vorgestellt.
1 Einleitung
Ein Bestandteil vieler komplexer Algorithmen ist es, aus einer Menge von Elementen die beiden zu finden, welche sich in bestimmten Eigenschaften am stärksten ähneln. Hierfür kann das ”FindingtheClosestPair of Points“-Problem herangezogen werden, indem man die Elemente entsprechend zweier Eigenschaften auf einer Ebene platziert. Das Punktepaar mit dem geringsten Abstand zueinander sind dann gerade die Elemente, welche sich in Bezug auf die beiden gewählten Eigenschaften am ähnlichsten sind. Es gibt aber auch direkte Anwendungen des Problems, zum Beispiel in der Flugsicherung: Die Gefahr einer Kollision ist dort am höchsten, wo sich zwei Flugzeuge am dichtesten beieinander befinden [[3] ]. Eine effiziente Lösung dieses Problems ist daher essentiell für viele Algorithmen.
2 Grundlagen
Thema dieser Ausarbeitung ist ein Algorithmus von M. I. Shamos und D. Hoey zur Lösung des the Closest Pair of Points“-Problems, welcher auf einem ”Finding ”Divide&Conquer“-Ansatzberuht.DieseArtvon Algorithmen löst ein gegebene Problem, indem es dieses zunächst in mehrere kleinere, oft auf triviale Weise zu lösende, Teilprobleme zerlegt. Aus diesen Teillösungen wird dann in einem nächsten Schritt die Lösung für das ursprüngliche Problem zusammengesetzt. Ein bekanntes ”Divide&Conquer“-Beispielistder Mergesort -Sortieralgorithmus.Hierwirddiezusortie- rende Liste immer weiter aufgeteilt, bis schließlich lediglich zwei Elemente sortiert wearden müssen. Dann werden zwei so sortierte Listen zusammengefügt, indem jeweils die ersten Elemente verglichen werden und das Minimum in die Rückgabeliste eingefügt wird. So wird jedes Element lediglich mit einem weiteren verglichen, weshalb das Zusammenfügen in linearer Zeit abläuft. Da zu Beginn das Problem immer halbiert wurde, müssen insgesamt log n Teilprobleme gelöst werden, was zu einer Gesamtlaufzeit von O (n log n) führt.
Entfernung“zweierb Punkte [Abbildung in dieser Leseprobe nicht enthalten]und [Abbildung in dieser Leseprobe nicht enthalten]wirdimFolgendendieeuklidischeDistanzAls
[Abbildung in dieser Leseprobe nicht enthalten]verwendet, prinzipiell lässt sich der vorgestellte Algorithmus aber für auch für andere Abstandsfunktionen verwenden3.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: Die Probleminstanz wird in zwei Teilprobleme aufgeteilt, wobei die Punktemenge anhand einer Trennli- nie L halbiert wird. Beim Zusammenführen der Teillösungen muss die δ -Umgebung von L genauer untersucht werden.
3 Der Algorithmus
3.1 Beschreibung
Um das ”Divide&Conquer“-Prinzipanwendenzukönnen,musseinegegebenePunktemengeinzwei möglichst gleich große Untermengen aufgeteilt werden können. Hierfür werden die Punkte zunächst anhand einer Koordinate sortiert, zum Beispiel mittels Mergesort. Nun wird die Problemgröße halbiert, indem die sortierte Punkteliste [Abbildung in dieser Leseprobe nicht enthalten] in zwei Listen [Abbildung in dieser Leseprobe nicht enthalten] [Abbildung in dieser Leseprobe nicht enthalten] unterteilt wird. Im Beispiel in Abbildung 1 werden die Punkte bezüglich der x-Koordinate sortiert, weshalb für de Teillisten die Bezeichnung[Abbildung in dieser Leseprobe nicht enthalten]gewählt wurde.
Diese Aufteilung wird so lange rekursiv fortgesetzt, bis die Teillisten nur noch aus maximal drei Elementen bestehen. Nun wird unter diesen Punkten das dichteste Punktepaar bestimmt, indem die Distanz aller Punkte zueinander berechnet wird. Der Rückgabewert dieses Rekursions-Basisfalles ist dann die gefundene minimale Distanz beziehungsweise je nach Implementierung auch die dazu gehörenden Punkte. Beim Zusammensetzten einer Lösung aus zwei Teillösungen werden dann die beiden Rückgabewerte [Abbildung in dieser Leseprobe nicht enthalten]und[Abbildung in dieser Leseprobe nicht enthalten]der Rekursionen verglichen und das Minimum [Abbildung in dieser Leseprobe nicht enthalten] gebildet.
Jetzt müssen lediglich noch die Punktepaare untersucht werden, bei welchen die beiden Punkte in jeweils unterschiedlichen Teilproblemen liegen, das heißt die Paare [Abbildung in dieser Leseprobe nicht enthalten]für die gilt [Abbildung in dieser Leseprobe nicht enthalten] links , [Abbildung in dieser Leseprobe nicht enthalten]. Of- fensichtlich reicht es hierfür aus, nur die Punkte zu beachten, welche in einer [Abbildung in dieser Leseprobe nicht enthalten] -Umgebung der Trennlinie liegen (Satz 1), weshalb zunächst diese Punkte bestimmt und entsprechend ihrer y-Koordinate sortiert wer- den. Die sortierte Liste dieser Punkte sei nun mit Sy 1 bezeichnet. Es muss nun also überprüft werden, ob es in der Liste Sy 1 zwei Punkte gibt, welche zueinander einen geringeren Abstand als δ haben. Wie gezeigt werden kann, reicht es hierfür aus, jeden Punkt in Sy 1 nur mit seinen 15 Nachfolgern zu vergleichen.
Werden in1mehrere solche Paare gefunden, wird dasjenige mit dem geringsten Abstand zurückgegeben. Wird kein solches Paar gefunden, so ist der Minimalabstand aller Punkte immer noch δ und es wird das Punktepaar zurückgegeben, welches in den Rekursionsaufrufen gefunden wurde.
[...]
- Citation du texte
- Thomas Hoffmann (Auteur), 2012, Finding the Closest Pair of Points (Divide and Conquer), Munich, GRIN Verlag, https://www.grin.com/document/264780
