| Mondays | 10:15-11:45 | Seminarraum 2 (Geometrie) (NT04064) |
| Wednesdays | 08:00-08:45 | Seminarraum 2 (Geometrie) (NT04064) |
| Wednesdays | 08:45-09:30 | Seminarraum 2 (Geometrie) (NT04064) |
This is an introductory course to discrete and computational geometry. We will study discrete structures such as polygons, convex hulls, triangulations, Voronoi diagrams, and more advanced topics. We will explore methods to analyse these structures, and efficient algorithms to process them.
Grading format: Final oral exam.
| [1] | Mark de Berg, Otfried Cheong, Marc Kreveld, and Mark Overmars. Computational Geometry. Algorithms and Applications (third edition). Springer, Berlin, 2008. |
| [2] | Satyan L. Devadoss and Joseph O'Rourke. Discrete and Computational Geometry. Princeton University Press, Princeton, 2011. |
(this is not final, it will be updated weekly)
| Date | Lecture notes | Exercises | Contents |
| Oct. 2 | Lecture 1 | Overview | |
| Oct. 7 | Lecture 2 | Exercise Sheet 1 | Polygons, triangulations Art Gallery Theorem |
| Oct. 9 | Lecture 3 | Exercise Sheet 2 | Art Gallery: algorithmic solution |
| Oct. 14 | Lecture 4 | Finished algorithm Triangulations in 2D: Further properties, convex polygons |
|
| Oct. 16 | Lecture 5 | Exercise Sheet 3 | Triangulations in 3D and higher dimensions Art Gallery in 3D Scissors congruence |
| Oct. 21 | Lecture 6 | Scissors congruence | |
| Oct. 23 | Lecture 7 | Exercise Sheet 4 | Convex hulls |
| Oct. 28 | Lecture 8 | Theorems about convex sets and point configurations: Radon, Tverberg, Helly, Caratheodory, and Separation. |
|
| Oct. 30 | Lecture 9 | Exercise Sheet 5 | Convex hull algorithms |
| Nov. 11 | Lecture 10 | Triangulations of point sets in the plane | |
| Nov. 13 | Lecture 11 | Exercise Sheet 6 | The associahedron, diameter and complexity |
| Nov. 18 | Cancelled | ||
| Nov. 20 | Lecture 12 | Exercise Sheet 7 | Angle optimal and legal triangulations |
| Nov. 25 | Lecture 13 | Voronoi diagrams | |
| Nov. 27 | Lecture 14 | Exercise Sheet 8 | Delaunay triangulations: Delaunay graphs |
| Dec. 2 | Lecture 15 | Delaunay triangulations The parabolic lift |
|
| Dec. 4 | Lecture 16 | Exercise Sheet 9 | Computation of Voronoi diagrams: Fortune's sweep-line algorithm |
| Dec. 9 | Lecture 17 | Computation of Delaunay triangulations Curve reconstruction |
|
| Dec. 11 | Lecture 18 | Exercise Sheet 10 | Line arrangements and duality |
| Dec. 16 | Lecture 19 | Duality: - Convex hulls and envelopes - Pseudoline arrangements - Triangulations for points in convex position |
|
| Dec. 18 | Lecture 20 | Exercise Sheet 11 | Pseudotriangulations |
| Jan. 8 | Lecture 21 | Exercise Sheet 12 | Pseudoline arrangements and pointed pseudotriangulations duality |
| Jan. 13 | Lecture 22 | Robot motion planning | |
| Jan. 15 | Lecture 23 | Exercise Sheet 13 | Minkowski sums complexity |
| Jan. 27 | Lecture 24 | Translational motion planning Visibility graphs |
|
| Jan. 29 | Lecture 25 | Computing the visibility graph Shortest paths for a translating polygonal robot |
Holidays and University Closings: Dec. 21-Jan. 6 (Weihnachtsferien).
Lectures cancelled: Weeks Nov. 4-8 and Jan. 20-24.