Sidebar
Discrete and Computational Geometry
MA-INF 1203 (WS 2020/2021)
Lecture Hours
| What | When | Where | Start | ECTS | Lecturer and Tutor |
|---|---|---|---|---|---|
| Lecture | Monday 16:00 - 17:30 | online | 2. November 2020 | 5,5 | Prof. Dr. Anne Driemel |
| Thursday 12:15 - 13:45 | online | ||||
| Tutorials | Tuesday 10:15 - 11:45 | online | 3. November 2020 | 3,5 | Frederik Brüning |
| Wednesday 14:15 - 15:45 |
Format
This is a 9 ECTS (270 h) course targeted at master-level Computer Science and Mathematics students. Because of the ongoing COVID-19 pandemic, the lecture material will be provided asynchronously via videos for download through eCampus. In addition, there will be live Zoom sessions where students can ask questions about the lecture material. These are further accompanied by weekly problem sets that students are expected to solve in independent self-study. The solutions to the problem sets are discussed in the tutorial hours via Zoom. Each student is expected to participate actively in these.
eCampus link: please register for the course here.
Content
Computational Geometry is the study of algorithmic problems for geometric data thereby touching upon a wide spectrum of application areas including computer graphics, geographic information systems, robotics, and others. The study of geometric algorithms often involves the combinatorial analysis of the complexity of geometric configurations. This has fundamental connections to the mathematical area of Discrete and Combinatorial Geometry which is also the topic of this course.
Topics which will be treated in this course:
- convex hull of a set of points
- Voronoi diagrams and nearest neighbor searching
- Delaunay triangulation
- hyperplane arrangements
- set systems and VC-dimension
- metric embeddings
- combinatorial complexity of geometric structures
- algorithms and data structures
Examination
Students have to hand in their written solutions for weekly problem sets (groups of up to two students each). At least 50% of the overall points have to be reached in order to be admitted to the final exam. There will be oral exams (most likely via Zoom) at the end of the semester. Exam dates (tentative): 22.02., 23.02., 24.02.2021
Literature
The basis of the course work are the lectures and assignments. For further reading we recommend the following books:
- Jiří Matoušek. Lectures on Discrete Geometry. Springer Graduate Texts in Mathematics. ISBN 0-387-95374-4.
- Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry — Algorithms and Applications (Third Edition). Springer. ISBN 978-3-540-77973-5.