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 11.02.2025 in SN 20.2. Please be there by 9:45 a.m. so that we can start on time. The entrance to the lecture hall is at the back of the Altgebäude, as shown here.

Mailing list

There is a mailing list for this class. Please sign up, as we will use it for communication. This list is moderated; participants from outside of TU Braunschweig will be approved manually, which may cause a slight initial delay. If you run into any problems, please contact Peter.

Material

You can find course material (slides, video recordings, and references) on the material page.

Homework