Geometrische Algorithmen in Haskell

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, dass mit 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.

Der Source-Code ist ebenfalls erhältlich. Alle Programme, die in der Arbeit erwähnt werden sind enthalten.