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.
| Subject | When | Where | Start | Lecturer |
|---|---|---|---|---|
| Lecture | Wednesday 10:30-12:00 and Friday 10:30-12:00 | LBH E08 | October 21st 2015 | Liu |
| Tutorial | Wednesday 12:00-13:30 and Friday 12:00-13:30 | LBH E08 | October 28th 2015 | Kang |
* 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
* Sheet 1: Geometry Duality and Finding the Minimum
* Sheet 2: Master Theorems and Voronoi Diagrams
* 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)