We will use the book Computational Geometry - Algorithms and Applications by de Berg, Cheong, van Kreveld, and Overmars, third edition, 2008. The course will treat most of Chapters 1-10, along with some other topics.
|Week||Date||Topic||Book||Slides||Exercises in book||Other notes|
|Week 17||April 25||Introduction||Chapter 1||slides 1||1.3, 1.6a, 1.7a-d, 1.9|
|April 27||No classes (Koningsdag)|
|Week 18||May 2||Line segment intersection (1/2)||Chapter 2 (part)||slides 2a||2.2, 2.3, 2.11, 2.12|
|May 4||Line segment intersection (2/2)||Chapter 2 (rest)||slides 2b||2.5-8, 2.13, 2.14|
|Week 19||May 9||Polygon triangulation||Chapter 3||slides 3||3.3, 3.4, 3.9, 3.12, 3.14|
|May 11||Linear programming||Chapter 4 (part)||slides 4a||4.1, 4.3, 4.7||Homework exam 1 distributed|
|Week 20||May 16||Smallest enclosing disks and more||Chapter 4 (rest)||slides 4b||4.10, 4.12, 4.14|
Homework exam 1 Q&A
(15.15-16.15, BBG 0.05)
|May 18||Range searching (1/2)||Chapter 5 (part)||slides 5a||5.1, 5.2, 5.5|
|Week 21||May 23||Range searching (2/2)||Chapter 5 (rest)||slides 5b||5.7, 5.8, 5.10, 5.11, 5.12||Hand in homework exam 1|
|May 25||No classes (Hemelvaartsdag)|
|Week 22||May 30||Voronoi diagrams (1/2)||Chapter 7 (part)||slides 7a||7.1, 7.5, 7.7, 7.10, 7.11|
|June 1||Planar point location||Chapter 6||slides 6||6.1, 6.3, 6.4, 6.5, 6.6||Homework exam 2 distributed|
|Week 23||June 6||Voronoi diagrams (2/2)||Chapter 7 (rest)||slides 7b||7.14, 7.15, 7.16|
Homework exam 2 Q&A
(15.15-16.15, BBG 0.05)
|June 8||Delaunay triangulations||Chapter 9||slides 9||9.2, 9.11, 9.12, 9.13, 9.16|
|Week 24||June 13||Arrangements
+ Research projects
|Chapter 8||slides 8
|8.2, 8.3, 8.4, 8.7, 8.8, 8.12, 8.15, 8.16||Hand in homework exam 2|
|June 15||Windowing queries||Chapter 10 (excluding
|slides 10||10.1, 10.9, 10.10|
|Week 25||June 20||Implementation||n/a||slides||n/a|
|June 22||Exam practice||Homework exam 2 returned|
|Week 26||June 27
|Final Exam, 13.30-16.30
The subject matter for the final exam consists of the following:
In one of the last sessions, Marc will give an overview of various research projects from the recent past. This will make use of some of the presentations listed below. These presentations are not exam material.
The final grade is based on two homework exams and one final exam. Each of these three items must be graded with at least a 5. Then the final grade is determined by the weighted average, where the exam counts for half and each of the homework exams for a quarter.
If one of the three items is graded (strictly) lower than 5, then you need a re-take. The grade for the final exam can be replaced by the grade for the re-take exam in July. If one of the homework exams has a grade lower than 5, then you can make a third homework exam after the final exam, whose grade will replace the grade lower than 5. If both of the homework exams have a grade lower than 5 (or you did not make them), then you automatically fail the course.
So, when you follow this course, there is a commitment to actively participate and you cannot wait until the final exam.
Below are the final exams from previous years. Note that some exams concerned slightly deviating material.
Just to see a previous year's first homework exam plus the comments I wrote after correcting it, see the 2011 first homework exam, and my comments on it.