This is an old revision of the document!


Discrete and Computational Geometry

MA-INF 1203 (WS 2019/2020)

Lecture Hours

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.)

Format

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.

Topics

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

Examination

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).

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.

Lecture Notes

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.

Exercises

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.

Assignments

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


Page Tools