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

Note: There will be no lectures on the dates: 2.12.2019, 23.12.2019-6.1.2020. There are no exercise sessions on 17.12.2019 and 18.12.2019.

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. Please register for the oral exam with our secretary Christiane Andrade (email: secret5@cs.uni-bonn.de, room 2.056, phone 0228-734327). You can register in the time period from from 1 December 2019 till 21 December 2019. The registration in BASIS must be done separately. The oral exams for the second trial will be in the period 24-26 March 2020.

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) (updated 6.11.2019)
• Assignment 3 (To be discussed: 29./30. Oct 2019)
• Assignment 4 (To be discussed: 05./06. Nov 2019)
• Assignment 5 (To be discussed: 12./13. Nov 2019)
• Assignment 6 (To be discussed: 19./20. Nov 2019)
• Assignment 7 (To be discussed: 26./27. Nov 2019)
• Assignment 8 (To be discussed: 03./04. Dec 2019)
• Assignment 9 (To be discussed: 10./11. Dec 2019)
• No Assignment in the week of 17./18. Dec 2019
• Assignment 10 (To be discussed: 7./8. Jan 2019)
• Assignment 11 (To be discussed: 14./15. Jan 2019)
• Assignment 12 (To be discussed: 21./22. Jan 2019)
• Assignment 13 (To be discussed: 28./29. Jan 2019)