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.
In this semester, we will try a special online format, with participant from different countries, giving us the opportunity to do international exchange in the same classroom. We will discuss how to make the best of this opportunity - so feel free to bring in new ideas and suggestions.

Topics are:

• Geometric problems and data structures
• Convex hulls
• Closest pairs
• Voronoi diagrams
• Delaunay triangulations
• Polygon triangulations
• Advanced research topics

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

Lectures

• Lecture #1, Oct 27, 2020 (Introduction)
• Video of Lecture #1
• Scientific Video: Coordinated Motion Planning
• Slides of Lecture #1
• Quiz Sheet #1
• Lecture #2, Nov 03, 2020 (Convex hull)
• Video of Lecture #2
• Slides of Lecture #2
• Quiz Sheet #2
• Original publications:
• Jarvis' March
• Quickhull
• Preparata/Hong
• Lecture #3, Nov 10, 2020 (Convex hull)
• Video of Lecture #3
• Slides of Lecture #3
• Quiz Sheet #3
• Original publications:
• Graham's Scan
• Kirkpatrick/Seidel
• Chan's algorithm
• Lecture #4, Nov 17, 2020 (Closest pair of points)
• Video of Lecture #4
• Slides of Lecture #4
• Quiz Sheet #4
• Original publications:
• Shamos / Bentley
• Ben-Or
• Compute Median
• Randomized Incremental Construction
• Lecture #5, Nov 24, 2020 (Closest pair of points)
• Video of Lecture #5
• Slides of Lecture #5
• Quiz Sheet #5
• Lecture #6, Dec 01, 2020 (Voronoi Diagram)
• Video of Lecture #6
• Slides of Lecture #6
• Lecture #7, Dec 08, 2020 (Voronoi Diagram)
• Live on Youtube at Tuesday, 15:00 CET

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 Christian Rieck.