Lecturing starts:

Thursday April 10th 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 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 April 10th
• Manuscript Lecture on April 15th
• Manuscript Lecture on April 17th
• Manuscript Lecture on April 22nd
• Manuscript Lecture on April 24th
• Manuscript Lecture on May 6th
• Manuscript Lecture on May 8th
• Manuscript Lecture on May 15th
• Manuscript Lecture on May 22nd
• Manuscript Lecture on May 27th
• Manuscript Lecture on June 3rd
• Manuscript Lecture on June 5th
• Some questions for the preparation of the oral exam (Misc)
• Some questions for the preparation of the oral exam (Voronoi Diagrams)

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 April 22nd and April 24th some additional questions and exercises will be discussed.

• Sheet 1: Dilation of Chains and Graphs (preparation until April 22nd)
• Sheet 2: Chan's technique/Lower bound (preparation until April 29th)
• Sheet 3: Randomized Algorithms for Geometric Structures (preparation until May 6th)
• Sheet 4: Randomized Algorithms for Geometric Structures II(preparation until May 13th)
• Sheet 5: Randomized Algorithms for Geometric Structures III and Abstract Voronoi Diagrams(preparation until May 20th)
• Sheet 6: Abstract Voronoi Diagrams II (preparation until May 27th)
• Sheet 7: Minkowskis Theorem and Applications (preparation until June 3rd)
• Sheet 8: Brunn Minkowski Inequality (preparation until June 17th)
• Sheet 9: Well separated pair decomposition (preparation until June 24th)
• Sheet 10: Spanner and WSPD (preparation until July 1st)

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

Mailinglist DCG