Rekursiv
In der Divide & Conquer-Variante geht es darum, die Punktmenge in jeweils kleinere Teilmengen zu verringern und das Closest-Pair-Problem somit in Teilaufgaben/Teilprobleme zu gliedern.
Zunächst wird die anfängliche Punktemenge in zwei etwa gleich große Hälften geteilt.
Ausgehend von dieser Teilung werden für beiden Hälften in Form rekursiver Aufrufe die jeweils
minimalsten Abstände zwischen zwei Punkten ermittelt und zwischengespeichert.
Anschließend wird in einem Vergleich die bisher geringste Distanz auf beiden Seiten berechnet
und für den nächsten Schritt verwendet.
In diesem wird, da die insgesamt geringste Distanz auch teilmengenübergreifend sein kann, um die
Trennlinie ein Rechteck gekennzeichnet, dessen Breite sowohl links als auch rechts der Trennlinie dem aktuell
minimalsten Abstand entspricht.
Um dies zu ermöglichen wurde bereits am Anfang eine zweite Punktmenge erzeugt, die alle Punkte
nach y-Koordinaten sortiert enthält.
Diese Liste wird nun durchlaufen und jeder Punkt mit all denen Punkten verglichen, die auf der
entsprechend anderen Seite der Trennlinie liegen und deren y-Koordinate sich von der des Punktes nicht
um mehr als das aktuelle Minimum unterscheidet.
Diese Einschränkungen bei den Vergleichen führt dazu, dass gegenüber dem BruteForce Ansatz deutlich weniger Vergleiche durchgeführt werden müssen und die Laufzeit somit von O(n²) auf O(n * log n) verringert werden kann.