Diploma thesis: "Geometric Algorithms in Haskell"

In my diploma thesis (written in German) i investigate the application of the functional programming paradigm in the context of geometric algorithms.



The implementation of geometric algorithms is often considered as difficult. This is due to the following three problems: inexact arithmetik, degenerated inputs and the correct implementation of complicated parts. The traditional method of software development is made responsible by researchers for the gap between theory and practice of geometric algorithms. We note, that the first two problems are caused by the nature of geometric problems and the last two problems by the methods of software development and the programming language used.



In the thesis is shown, that complex geometric algorithms can be implemented short, modular und with a high degree of abstractness in the functional programming language Haskell. Therefore functional programming posesses the potential to reduce the two last mentioned problems.



We implement

• Basic datastructures for points, lines, segments, rays, polygons and simple functions like calculations of angles, area, etc.
• datastructures for efficient orthogonal range queries: kd-trees and rangetrees
• algorithms for twodimensional convex hulls: Jarvis March, Grahams Scan, Merge-Hull, the algorithm of Kirkpatrick and Seidel and Chan's algorithmus
• algorithms for the triangulation of simple polygons: two simple but inefficient algorithms, the "standard"-algorithm of Garey, Johnson, Preparata and Tarjan and two output-sensitive algorithms of Toussaint
• the quad-edge data structure (QEDS) for planar subdivisions and polyhedra
• algorithms for Delaunay-triangulations and Voronoi-diagrams in two dimensions: the divide & conquer-algorithms of Stolfi and Guibas, which uses the QEDS and a randomised incremental algorithms by Boissonnat and Teillaud, which uses the delaunay-dag.
• and some applications in two dimensions, like all-next-neighbors, the next post office, the largest empty circle and the closest pair in any dimension.

The thesis is written in German, but probably it is of use for anyone with basic knowledge in functional programming and/or geometric algorithms.

The thesis is available in the following formats.

• Portable Document Format PDF (962 KB)
• PostScript (compressed with gzip) .ps.gz(566 KB)

The Haskell sources are available separately. All programs mentioned above and documentation about installation are included.