What | When | Where | Start | ECTS | Lecturer and Tutor |
---|---|---|---|---|---|

Lecture | Monday 12:15 - 13:45 | Hörsaalzentrum Pöppelsdorf, room 3 | 10 October 2022 | 5,5 | Dr. Herman Haverkort |

Wednesday 12:15 - 13:45 | Hörsaalzentrum Pöppelsdorf, room 7 | ||||

Tutorials | Tuesday 10:15 - 11:45 | Institut für Informatik, room 2.050 | 18 October 2022 | 3,5 | Anna Heuser |

Wednesday 14:15 - 15:45 | Institut für Informatik, room 2.050 |

This is a 9 ECTS (270 h) course targeted at master-level Computer Science and Mathematics students. There will be two lectures each week. These are 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 sessions. Each student is expected to participate actively in these.

Please register for the course on eCampus. Course materials and up-to-date information on course organisation will also be provided on eCampus.

Computational Geometry is the study of algorithmic problems for geometric data. Thereby it touches 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, from which we will also study several topics in this course.

Topics which will be treated in this course include:

- convex hulls in two and more dimensions
- Voronoi diagrams and nearest-neighbour searching
- Delaunay triangulations
- hyperplane arrangements
- set systems and VC-dimension
- metric embeddings
- combinatorial complexity of geometric structures
- algorithms and data structures related to these topics

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 (hopefully in the institute, but via Zoom if necessary) at the end of the semester.

The basis of the course work are the lectures and assignments. Lecture notes for all lectures will be available on eCampus. 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.