• 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

Organisation

  • 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

Topics

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

Homework

Lecture Slides

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

Literature

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: