• Design and Analysis of Algorithms Part 3 - Computational Geometry

    PhD course

This course is the third in a series of three, where each course can be taken independently:
Part 1: Mathematical Tools and Network Problems ([DAA1, 2019], [DAA1, 2017])
Part 2: Approximation and Online Algorithms ([DAA2, 2018])
Part 3: Computational Geometry


  • The course will be based on this course.
  • There is no time fixed yet for the course, if you are interested in taking the course, please send an email to Christiane.
  • Lecturer: Christiane Schmidt

Current Stuff

  • Welcome to the class!
  • There is a nice overview on proof techniques, all with a common example, from Estie Arkin available [here].

Course Content


  • The Art Gallery Problem and Polygon Triangulations
  • Convex Hulls
  • Triangulation of Point Sets
  • Voronoi Diagrams
  • Point Location


Lecture Slides

  • Slides are password protected!
  • The password will be announced in the first seminar.


The course is self-contained, that is, the lecture notes and other course material will be enough to follow the course. For the group presentation material will be made available. Interested students may use the following books for additional self-study: