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

Geometry: Combinatorics and 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.

Complete Lecture Notes

Everything in one PDF (261 pages).

Individual Chapters

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