Computational Geometry (Algorithmische Geometrie)

Geometric algorithms are of fundamental interest for a large spectrum of topics, both from theory and practice. In this class, we will start from the basic foundations, and work our way towards advanced topics.

The participants learn the basic concepts of geometric algorithms. They know how to gauge the difficulty of geometric problems and formulate appropriate objectives. They are able to master different solution techniques and are capable of developing algorithmic methods for new challenges. They understand the practical relevance of problems and solutions.

Topics are:

• Geometric problems and data structures
• Convex hulls
• Closest pairs
• Voronoi diagrams
• Polygon triangulation
• Point triangulation
• Location problems
• Tours and polygons

• Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried Schwarzkopf: Computational Geometry: Algorithms and Applications, Second. Aufl., Seite 367, Springer-Verlag, 2000 (deBerg2000, BibTeX)
• Rolf Klein: Algorithmische Geometrie, Seite 1-355, examen.press, 1997 (Klein1997, BibTeX)
• Franco P. Preparata and Michael Ian Shamos: Computational Geometry: An Introduction, Springer, 1985 (Preparata1985, BibTeX)

Final exam

The written exam will take place on 02.03.2026 in PK 4.122. Please be there by 8:45 a.m. so that we can start on time.

Organization

If you run into any problems, please contact Peter.

• There is a mailing list for this class. Please sign up, as we will use it for communication. This list is moderated which may cause a slight delay upon registration.
• You can find course material (slides, video recordings, and references) on the material page.

Homework

Details one the coursework ("Studienleistung") will be announced in the first big tutorial.