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)

Lectures

• Lecture #1, Nov 02, 2023 (Introduction)
  • Video from previous year: [Youtube]
  • Slides: [Download]
  • Original publications: Shamos / Bentley, Ben-Or, Compute Median
• Lecture #2, Nov 07, 2023 (Convex hull)
  • Video from previous year: [Youtube]
  • Slides: [Download]
  • Original publications: Jarvis' March, Quickhull
• Lecture #3, Nov 14, 2023 (Convex hull)
  • Video from previous year: [Youtube]
  • Slides: [Download]
  • Original publications: Preparata/Hong, Graham's Scan, Kirkpatrick/Seidel, Chan's algorithm
• Lecture #4, Nov 21, 2023 (Closest pairs of points)
  • Video from previous year: [Youtube]
  • Slides: [Download]
  • Original publications: Shamos / Bentley, Ben-Or, Compute Median
• Lecture #5, Nov 28, 2023 (Closest pairs of points)
  • Video from previous year: [Youtube]
  • Slides: [Download]
  • Original publications: Randomized Incremental Construction
• Lecture #6, Dec 5, 2023 (Voronoi diagram)
  • Video from previous year: [Youtube]
  • Slides: [Download]
• Lecture #7, Dec 12, 2023 (Voronoi diagram)
  • Video from previous year: [Youtube]
  • Slides: [Download]
• Lecture #8, Dec 19, 2023 (Voronoi diagram)
  • Video from previous year: [Youtube]
  • Slides: [Download]
  • Original publications: Fortune's Algorithm
• Lecture #9, Jan 9, 2024 (Voronoi games)
  • Video from previous year: [Youtube]
  • Slides: [Download]
  • 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 16, 2024 (Polygon triangulation)
  • Video from previous year: [Youtube]
  • Slides: [pdf]
  • Original publications: Robot Triangulation, Chazelle 1991, Clarkson 1989, Garey 1978, Kirkpatrick 1992, Tarjan 1988
• Lecture #11, Jan 23, 2024 (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 30, 2022 (Location problems)
  • Video: [Youtube]
  • 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 06, 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

Tutorials

• Tutorial #1, Nov 16, 2023 (Introduction, Convex Hulls)
  • Slides: [Download]
  • Further references:
    • Point Location Problem (Shamos, 1975) [Download, Problem 4]
• Homework Sheet #1
  • Due Dec 21, 2023
  • [Download]
• Tutorial #2, Nov 23, 2023 (Convex Layers, Boolean Operations)
  • Slides: [Download]
  • References:
    • Convex Layers (Chazelle, 1985) [Download]
• Tutorial #3, Dec 7, 2023 (Moved to IZ305)
  • Slides: [Download]
  • References:
    • Rotating Callipers Algorithm (Shamos, 1975) [Download, Problem 3]
• Tutorial #4, Dec 21, 2023 (Scissors Congruence, Higher order Voronoi diagram)
  • Slides: [Download]
  • References:
    • Visualizing Scissors Congruence (Devadoss et al., 2016) [Download]
• Homework Sheet #2
  • Due Feb 1, 2023
  • [Download]
• Tutorial #5, Jan 11, 2024
  • Slides: [Download]
• Tutorial #6, Jan 25, 2024 (The Art Gallery Problem)
  • Slides: [Download]
• Tutorial #7, Feb 22, 2024
  • Exam preparation!
  • Slides: [Download]

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.