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