Lecturing starts:

Wednesday April 8th at 14:30 am in E08 LBH!

Within this course we consider randomized algorithms for geometric structures. We first talk about the general concept of randomized incremental, divide-and-conquer, and dynamic techniques, and use basic geometric structures for illustrations. Then we apply these techniques to more advanced geometric structures and have further discussion. The course is based on the book of Ketan Mulmuley on Computational Geometry: An Introduction Through Randomized Algorithms, and several selected papers. There will be biweekly exercises that have to be solved by the participants and they will be discussed in the tutorials.

• Manuscript Lecture on QuickSort
• Manuscript Lecture on Trapezoidal Decomposition
• Manuscript Lecture on General Concept for Incremental Construction (updated May 6)
• Manuscript Lecture on Voronoi Diagrams and Delaunay Triangulations (updated May 19)
• Manuscript Lecture on Configuration Space
• Manuscript Lecture on Random Sampling
• Manuscript Lecture on Top-Down Sampling
• Manuscript Lecture on Bottom-Up Sampling
• Sample Questions for Final Exams

• Sheet 1: Quicksort and Trapezoidal Decomposition (preparation until April 29th)
• Sheet 2: Triangulation and Convex Hull (preparation until May 13th. **updated on May 1 especially for exercise 5**)
• Sheet 3: Voronoi Diagrams and Delaunay Triangulation (preparation until June 3rd)
• Sheet 4: Configuration Space and Random Sampling (preparation until June 24th)
• Sheet 5: Top-Down Sampling (preparation until July 8th)

* Time Slots on July 30