Unsere Aufgabe
bestand darin, zwei Algorithmen in C++ zu implementieren,
die jeweils die kürzeste Distanz zweier Punkte finden, sowie die
dazugehörigen Punkte ausgeben sollte.
Das Closest Pair Problem sollte hierbei in zwei verschiedenen Arten
behandelt und visualisiert werden:
Einmal der sog. „Sweep“-Algorithmus (iterative Lösung), zum anderen mit Hilfe
eines Divide&Conquer-Verfahren (rekursive Lösung).
Konkret
bedeutet dies, dass in einer beliebigen Menge von Punkten in einem 2-dimensionalen Raum das Paar gefunden werden soll, welches die geringste Distanz aufweist. Dieses Paar soll graphisch gekennzeichnet sein und die daraus resultierenden Daten zurückgegeben werden. Dies soll natürlich möglichst effizient geschehen, d.h. in kleinster Laufzeit. Zur Visualisierung haben wir die LEDA-Bilbliotheken verwendet.