Department of Computer Science | Institute of Theoretical Computer Science | Theory of Combinatorial Algorithms

This page hosts the lecture notes for the corresponding course from 2018.

We intend to update it for future iterations of the course, which typically takes place every year Sep-Dec.

Comments are welcome, regardless of whether it is a minor typo or punctuation error, a glitch in formulation, or a hole in an argument. So if you find anything, please tell Michael Hoffmann.

Everything in one PDF (261 pages).

- Chapter 1: Fundamentals
- Model of Computation, Geometric Objects, Graphs
- Chapter 2: Plane Embeddings
- Drawings, Embeddings, Planarity, Graph Representations, Combinatorial Embeddings, Unique Embeddings, Triangulations, Compact Straight-Line Embeddings, Canonical Orderings
- Chapter 3: Polygons
- Classes of Polygons, Polygon Triangulations, The Art Gallery Problem
- Chapter 4: Convex Hull
- Convexity, Classical Theorems for Convex Sets, Planar Convex Hull, Jarvis’ Wrap, Graham Scan, Chan’s Algorithm
- Chapter 5: Delaunay Triangulations
- Empty Circle Property, Lawson Flip Algorithm, Lifting Map, Delaunay Graph, Angle Maximization, Constrained Triangulations
- Chapter 6: Delaunay Triangulation: Incremental Construction
- History Graph, Structural Changes
- Chapter 7: Voronoi Diagrams
- Post Office Problem, Duality, Lifting Map, Planar Point Location, Kirkpatrick’s Hierarchy
- Chapter 8: Line Arrangements
- Construction, Zone Theorem, The Power of Duality, Rotation Systems, 3-Sum, Segment Endpoint Visibility Graphs, Ham Sandwich Theorem, Constructing Ham Sandwich Cuts in the Plane, Davenport-Schinzel Sequences, Constructing Lower Envelopes, Complexity of a Single Face
- Chapter 9: Counting
- Embracing k-Sets, h-vectors, Simplicial Depth
- Chapter 10: Crossings
- The Crossing Lemma, Szemerédi-Trotter, Unit Distances, Sum-Product Sets
- Appendix A: Line Sweep
- Line Segment Intersection, Simple Polygon Testing, Map Overlay, Algebraic Degree of Geometric Primitives, Red-Blue Intersections
- Appendix B: The Configuration Space Framework
- Configuration Spaces, Expected Structural Change, Conflict Counting
- Appendix C: Trapezoidal Maps
- Incremental Construction, Point Location, Line Segment Intersection, Simple Polygon Triangulation
- Appendix D: Translational Motion Planning
- Configuration Space, Minkowski Sums, Constructing a Single Face
- Appendix E: Linear Programming
- Linear Separability of Point Sets, Minimum Area Enclosing Annulus
- Appendix F: A Randomized Algorithm for Linear Programming
- Helly’s Theorem, Violation Tests, Basis Computations
- Appendix G: Smallest Enclosing Balls
- Welzl's Algorithm, Swiss Algorithm, Forever Swiss Algorithm, SEB for Manhattan Distances
- Appendix H: Epsilon Nets
- Range Spaces, VC-Dimension, Small Epsilon-Nets