In meiner Arbeit untersuche ich die Potentiale der funktionalen Programmierung
bei der Implementierung von geometrischen Algorithmen.
Die Implementierung von geometrischen Algorithmen gilt im Allgemeinen als
schwierig. Dieses wird auf drei Probleme zurückgeführt: inexakte Arithmetik, degenerierte
Eingaben und die korrekte Implementierung schwieriger Teile.
Auch wird die traditionelle Methode der Softwareentwicklung - zum Teil - für die Lücke zwischen
Theorie und Praxis der geometrischen Algorithmen verantwortlich gemacht.
Während die ersten beiden Probleme ihre Ursachen in der Natur geometrischer
Probleme haben, werden die letzten beiden Probleme durch die Methodik der Softwareerstellung
und durch die verwendete Programmiersprache beeinflusst.
In dieser Arbeit zeigen wir, dassmit funktionalen Programmiersprachen auch
komplexe geometrische Algorithmen kurz, modular und mit einem hohen Abstraktionsgrad
dargestellt werden können und dass sie somit das Potential haben, die
letzten beiden genannten Probleme zu reduzieren.
Implementiert wurden die folgenden Funktionen und Datentypen.
-
Datenstrukturen für Punkte, Geraden, Strecken, Strahlen, Polygone und einfache Funktionen, wie
z. B. die Berechnung von Winkeln, von Flächeninhalten, etc.
-
Effiziente orthogonale Bereichsabfragen mit KD-Bäumen und Bereichsbäume (Rangetrees).
-
Zweidimensionale konvexe Hüllen mit Jarvis March, Grahams Scan, Merge-Hull, den Algorithmus von
Kirkpatrick und Seidel und Chan's Algorithmus
-
Triangulationen von einfachen Polygonen: zwei naive Algorithmen, der "Standard"-Algorithmus von Garey,
Johnson, Preparata and Tarjan sowie zwei ausgabesensitive von Toussaint
-
Die Quad-Edge-Datenstruktur (QEDS) für planare Zerlegungen und Polyeder.
-
Delaunay-Triangulationen und Voronoi-Diagramme in zwei Dimensionen: Der Divide & Conquer - Algorithmus
von Stolfi und Guibas, der die QEDS benutzt und einen randomisierten, inkrementellen Algorithmus von
Boissonnat und Teillaud, der den sog. Delaunay-DAG verwendet.
-
Einige Anwendungen in zwei Dimensionen, wie z.B. alle nächsten Nachbarn, das nächste Postamt,
der größte leere Kreis und in beliebigen Dimensionen das dichteste Punktepaar.
