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 | 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 |
| The Art Gallery Problem | [PDF] | A linear algorithm for computing the visibility polygon from a point |