Hier werden Videoaufnahmen der Vorlesung von 2021 zur Verfügung gestellt. Diese allein können eine Teilnahme an der Vorlesung im laufenden Semester nicht ersetzen: Die Kursstruktur kann abweichen.
| 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 |
| Topic | Tutorial Material | References |
|---|---|---|
| Organisation and Convex Hulls | [PDF] | Big O Notation (DE, IBR), Big O Notation (EN, MIT OpenCourseWare) |
| Jordan Curves and Convex Hulls | [PDF] | Jordan Polygon Theorem, Winding Number |
| Farthest pairs | [PDF] | Dissertation of Michael Shamos |
| 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 |