Geometry: Combinatorics & Algorithms

September 2021–February 2022

Geometry: Combinatorics & Algorithms

These notes are based on a course under the same title at ETH Zürich, plus some personal readings. The main sources are the lecture notes of the course, Graph Theory by Reinhard Diestel, and Lectures on Polytopes by Günter M. Ziegler.

Parts I and II are handwritten. Part III is available in html format.

I. Planar Embeddings

  1. Planarity
  2. Euler’s formula
  3. Planarity test
  4. Maximal planar graphs & triangulation
  5. Unique embedding
  6. Straightening an embedding
  7. Crossing number

II. Geometry of 2D Points and Lines

  1. Polygons
  2. Convexity
  3. Convex hulls
  4. Algorithms for 2D convex hulls
  5. Detour: Jensen’s inequality
  6. Triangulation of point sets
  7. Delaunay triangulation
  8. Voronoi diagram
  9. Fast construction of Delaunay
  10. Duality & line arrangement

III. Convex Polytopes

  1. Polytopes
  2. Main theorem
  3. Farkas’ lemma
  4. Face Lattice
  5. Counting faces
Return↩︎