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

Lecture | Monday 16:00 - 17:30 | CP1-HSZ HS7 | 7. October 2019 | 5,5 | Prof. Dr. Anne Driemel Dr. Herman Haverkort |

Thursday 12:15 - 13:45 | CP1-HSZ HS4 | ||||

Exercise | Tuesday 10:15 - 11:45 | INF 2.050 | 15. October 2019 | 3,5 | Ioannis Psarros |

Wednesday 14:15 - 15:45 |

(By popular request we changed the starting time of the Monday lecture from 16:15 to 16:00.)

This is a 9 ECTS (270 h) course targeted at master-level Computer Science and Mathematics students. The lectures 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 exercise hours. Each student is expected to participate actively in these.

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.

The following is a list of preliminary topics for this course:

- fundamentals of convex sets
- convex polytopes
- Voronoi diagrams
- hyperplane arrangements
- randomised incremental construction
- data-structures for range searching (simplex and orthogonal)
- data-structures for point location
- intersection patterns and transversals
- VC-dimension of range spaces
- the epsilon-net theorem
- metric embeddings
- well-separated pairs decomposition
- spanners

We will have oral exams at the end of the semester. The first set of exam dates will be in the period 11-13 February 2020. More information will follow in due time.

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.

Lecture notes will be made available (with some delay) through ecampus . In order to access them please follow the link and register for the course there. It is strongly recommended that you attend the lectures and take your own notes. We do not guarantee that lecture notes will be posted for all lectures.

The lectures are accompanied by exercises (see the schedule above). We will post weekly assignments. You are expected to work on these independently and prior to the exercise hours. This constitutes a considerable portion of the course work. Solutions and feedback can be given during the exercise hours.

We will upload the assignments here. The first exercise will take place on 15 Oct 2019 (second week).

- Assignment 1 (To be discussed: 15./16. Oct 2019)
- Assignment 2 (To be discussed: 22./23. Oct 2019)
- Assignment 3 (To be discussed: 29./30. Oct 2019)