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.

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

* Manuscript Lecture on Lattices and Minkowski's Theorem

* Sample Questions for the Final Exam

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.

• Sheet 1: Randomized Algorithms for Geometric Structures (preparation until October 21st and updated for exercise 3 on October 16th)

• Sheet 2: Randomized Algorithms for Geometric Structures II (preparation until October 28th)

• Sheet 3: Randomized Algorithms for Geometric Structures III (preparation until November 4th)

• Sheet 4: Randomized Algorithms for Geometric Structures IV (preparation until November 11th)

• Sheet 5: Dynamic Setting and Chan's Randomized Technique (preparation until November 18th)

• Sheet 6: Dilations (preparation until November 25th)

• Sheet 7: Chan's technique and Dilations (preparation until December 2nd)

• Sheet 8: Properties for Abstract Voronoi Diagrams (preparation until December 9th)
• Sheet 9: Construaction for Abstract Voronoi Diagrams (preparation until December 16th)
• Sheet 10: Properties for kth-order Voronoi Diagrams (preparation until January 20th)

Please join the Mailinglist for getting relevant information during the semester.

Mailinglist DCG