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
• 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)

Lectures

• Lecture #1, Nov 01, 2022 (Introduction)
  • Video from last year: [Youtube]
  • Slides: [pdf]
  • Scientific video: Coordinated Motion Planning
• Lecture #2, Nov 08, 2022 (Convex hull)
  • Video from last year: [Youtube]
  • Slides: [pdf]
  • Original publications: Jarvis' March, Quickhull
• Lecture #3, Nov 15, 2022 (Convex hull)
  • Video: [Youtube]
  • Slides: [pdf]
  • Original publications: Preparata/Hong, Graham's Scan, Kirkpatrick/Seidel, Chan's algorithm
• Lecture #4, Nov 22, 2021 (Closest pair of points)
  • Video: [Youtube]
  • Slides: [pdf]
  • Original publications: Shamos / Bentley, Ben-Or, Compute Median
• Lecture #5, Nov 29, 2022 (Closest pair of points)
  • Video: [Youtube]
  • Slides: [pdf]
  • Original publications: Randomized Incremental Construction
• Lecture #6, Dec 06, 2022 (Voronoi diagram)
  • Video: [Youtube]
  • Slides: [pdf]
• Lecture #7, Dec 12, 2022 (Voronoi diagram)
  • Video: [Youtube]
  • Slides: [pdf]
• Lecture #8, Dec 19, 2022 (Voronoi diagram)
  • Video: [Youtube]
  • Slides: [pdf]
  • Original publications: Fortune
• Lecture #9, Jan 10, 2023 (Voronoi games)
  • Video: [Youtube]
  • Slides: [pdf]
  • Original publications: Ahn 2001, Ahn 2004, One-Round Voronoi Game, Cheong 2007, Muller / Preparata, Teramoto 2011, Voronoi Game on Graphs, One-Round Manhattan Voronoi Game
• Lecture #10, Jan 17, 2022 (Polygon triangulation)
  • Video: [Youtube]
  • Slides: [pdf]
  • Original publications: Robot Triangulation, Chazelle 1991, Clarkson 1989, Garey 1978, Kirkpatrick 1992, Tarjan 1988
• Lecture #11, Jan 24, 2022 (Point triangulation)
  • Video: [Youtube]
  • Slides: [pdf]
  • Original publications: Delaunay, Triangulations - ETH, MaxMin Angle, MinMax Angle, Mulzer-Rote MWT, Haas MWT, MaxMin Edge Length, MinMax Edge Length
• Lecture #12, Jan 31, 2022 (Location problems)
  • Video: [IBR]
  • Slides: [pdf]
  • Original publications: Continuous Weber Problem, Continuous Fermat Weber Problem, Solving Hard to Approximate Easy, Median, Algebraic Degree of Geometric Optimization, Paths Among Obstacles, Impossibility of Solving Fifth Degree Equation (French)
• Lecture #13, Feb 07, 2023
  • Video: [Youtube]
  • Slides: [pdf]
  • Original publications: Hamiltonian Cycles in Grid Graphs, MaxTSP (Russian), MaxTSP, Lawn Mowing and Milling, Min Stars Max Matching, Solving Hard to Approximate Easy, Geometric Max TSP, Longest Geometric Tours, Non-Simple Polygons with Min Perimeter, Cycle Cover with Turn Cost

Exercise / discussion meetings

• Meeting #1, Nov 10, 2022 // Slides, Euler characteristic, Four color theorem
• Meeting #3, Dec 08, 2022 // Slides, Rotating calipers
• Exercise Sheet #1, Dec 08, 2022, due on Jan 12, 2023 // Download
• Meeting #4, Dec 15, 2022 // Slides, Farthest-point Voronoi diagram & Smallest enclosing circle, Fold and Cut, Abstract Voronoi diagrams - Rolf Klein
• Meeting #5, Jan 12, 2023 // Trapezoidal maps - Seidel
• Exercise Sheet #2, Jan 12, 2023, due on Jan 26, 2023 // Download
• Meeting #6, Jan 26, 2023 // Slides, How to guard a museum

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 Michael.