• The expected day of the oral exam is Feb 26 (Fri).
• There is no lecture on Feb 12.
• Sample questions are here
• Schedule for the oral exam is here. Please send me an email to confirm your time slot by Feb 19. (chliu@uni-bonn.de)

Within this course we consider discrete geometric problems and discuss structural properties and the computational complexity. The course is based on the book of Jiri Matousek on Lectures on Discrete Geometry and selected papers. There will be weekly exercises that have to be solved by the participants and they will be discussed in the tutorials.

* Manuscript Lecture on Introduction and Geometric Duality

* Manuscript Lecture on Chan's Randomized Technique

* Manuscript Lecture on Voronoi Diagrams

* Manuscript Lecture on Geometric Detour

* Manuscript Lecture on Randomized Algorithm for Geometric Detour (updated Nov 16)

* Manuscript Lecture on Properties of Abstract Voronoi Diagrams

* Manuscript Lecture on Construction of Abstract Voronoi Diagrams

* Manuscript Lecture on Order-k Voronoi Diagrams

* Manuscript Lecture on Convexity

* Manuscript Lecture on Lattices

* Manuscript Lecture on Convex Polytope

* Manuscript Lecture on Faces of Convex Polytopes

* Manuscript Lecture on Number of Faces in Convex Polytopes

* Manuscript Lecture on Arrangement of Hyperplanes

* Manuscript Lecture on Zone Theorem

* Sheet 1: Geometry Duality and Finding the Minimum

* Sheet 2: Master Theorems and Voronoi Diagrams

* Sheet 3: Geometric Detour

* Sheet 4: Chan's Technique and Detours (updated on Nov 20)

* Sheet 5: Abstract Voronoi Diagrams (deadline: Friday Dec 4)

* Sheet 6: Order-k Voronoi diagrams (deadline: Friday Dec 16)

* Sheet 7: Convexity (deadline: Friday Jan 15)

* Sheet 8: Lattices (deadline: Friday Jan 22)

* Sheet 9: Convex Polytope (deadline: Friday Jan 29)

* Sheet 10: Last Exercise (deadline: Friday Feb 5)