Lecturing starts:
Thursday October 9th at 10:30 am in E08 LBH!
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 the book of Ketan Mulmuley on Computational Geometry: An Introduction Through Randomized Algorithms but also makes use of other sources. There will be weekly exercises that have to be solved by the participants and they will be discussed in the tutorials.
When | Where | Start | CP | Lecturer |
---|---|---|---|---|
Tuesday 10:30-12:00 and Thursday 13:00-14:30 (except Nov. 13) | LBH E08 | October 9th 2014 | 5,5 | Liu |
Tutorials | October 21th 2014 | 3,5 | Delonge |
Here you will find additional material during the lecture, scientific articles, hints on textbooks or simply scans of a handwritten manuscript.
* Manuscript Lecture on QuickSort
* Manuscript Lecture on Vertical Trapezoidal Decomposition
* Manuscript Lecture on Voronoi Diagrams
* Manuscript Lecture on General Ideas for Randomized Incremental construction
* Manuscript Lecture on Dynamic Setting
* Manuscript Lecture on Chan's Randomized Techniques
* Manuscript Lecture on Geometric Dilation
* Manuscript Lecture on Randomized Algorithm for Geometric Dilation
* Manuscript Lecture on Properties for Abstract Voronoi Diagrams
* Manuscript Lecture on Construction for Abstract Voronoi Diagrams
* Manuscript Lecture on Geometric Duality
* Manuscript Lecture on Properties for kth-order Voronoi diagrams
* Manuscript Lecture on Convexity
Due to the announced conditions participants have to solve at least half of the exercises successfully and have to present at least two correct solutions in the tutorials. In the first tutorials on October 21 and October 23 some additional questions and exercises will be discussed.
Please join the Mailinglist for getting relevant information during the semester.