We provide video recordings of the lectures from 2021 below. These alone cannot replace attendance in the ongoing semester: The course structure may differ in some parts.
| Topic | Lecture Material | References |
|---|---|---|
| Introduction | [PDF] [Video] | |
| Convex Hull I | [PDF] [Video] | Jarvis' March, Quickhull |
| Convex Hull II | [PDF] [Video] | Preparata/Hong, Graham's Scan, Kirkpatrick/Seidel, Chan's algorithm |
| Closest Pairs of Points I | [PDF] [Video] | Shamos / Bentley, Ben-Or, Compute Median |
| Closest Pairs of Points II | [PDF] [Video] | Randomized Incremental Construction |
| Voronoi diagrams I | [PDF] [Video] | |
| Voronoi diagrams II | [PDF] [Video] | |
| Voronoi diagrams III | [PDF] [Video] | Fortune's Algorithm |
| Voronoi games | [PDF] [Video] | Ahn 2001, Ahn 2004, One-Round Voronoi Game, Cheong 2007, Muller / Preparata, Teramoto 2011, Voronoi Game on Graphs, One-Round Manhattan Voronoi Game |
| Polygon Triangulation | [PDF] [Video] | Robot Triangulation, Chazelle 1991, Clarkson 1989, Garey 1978, Kirkpatrick 1992, Tarjan 1988 |
| Point Triangulation | [PDF] [Video] | Delaunay, Triangulations - ETH, MaxMin Angle, MinMax Angle, Mulzer-Rote MWT, Haas MWT, MaxMin Edge Length, MinMax Edge Length |
| Topic | Tutorial Material | References |
|---|---|---|
| Organisation and Convex Hulls | [PDF] | Big O Notation (DE, IBR), Big O Notation (EN, MIT OpenCourseWare) |
| Farthest pairs | [PDF] | Dissertation of Michael Shamos |
| Jordan Curves and Convex Hulls | [PDF] | Jordan Polygon Theorem, Winding Number |
| Voronoi diagrams and Enclosing disks | [PDF] | Optimal deterministic algorithms for 2d and 3d shallow cuttings, An optimal algorithm for higher-order Voronoi diagrams in the plane: The usefulness of nondeterminism, Farthest-polygon Voronoi diagrams |
| Convex hull of simple polygons and Algorithm design | [PDF] | On-line Construction of the Convex Hull of a Simple Polyline |