We provide video recordings of the lecture from 2021 below. These alone cannot replace attendance in the ongoing semester: The course structure may differ.
| 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] |
| 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 |