Geometric Algorithms, block 3, 2016 (under construction)

Lecturer: Marc van Kreveld (


Course literature

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 the chapters 1-9, a little bit of chapter 10, and some other topics.

Schedule of 2016, tentative:

Week 6 Feb 9 Introduction Chapter 1 slides 1 Exercises: 1.3, 1.6a, 1.7a-d, 1.9
Feb 11   Line segment intersection Chapter 2 (part) slides 2a Exercises: 2.2, 2.3, 2.11, 2.12
Week 7 Feb 16 Line segment intersection Chapter 2 (rest) slides 2b Exercises: 2.5-8, 2.13, 2.14
Feb 18 Polygon triangulation Chapter 3 slides 3 Exercises: 3.3, 3.4, 3.9, 3.12, 3.14 Homework exam 1 distributed
Week 8 Feb 23 Linear programming Chapter 4 (part) slides 4a  Exercises: 4.1, 4.3, 4.7
Feb 25 Smallest enclosing disks and more   Chapter 4 (rest) slides 4b Exercises: 4.10, 4.12, 4.14
Week 9 Mar 1 Range searching Chapter 5 (part) slides 5a Exercises: 5.1, 5.2, 5.5 Hand in homework exam 1
Mar 3 Range searching Chapter 5 (rest) slides 5b slides 10 Exercises: 5.7, 5.8, 5.10, 5.11, 5.12
Week 10 Mar 8 Discussion of homework 1 Exercises
Mar 10 Voronoi Diagrams Chapter 7 (part) slides 7a Exercises: 7.1, 7.5, 7.7, 7.10, 7.11
Week 11 Mar 15 More on Voronoi Diagrams Chapter 7 (rest) slides 7b Exercises: 7.14, 7.15, 7.16 Homework exam 2 distributed  
Mar 17 Planar point location Chapter 6 slides 6 Exercises: 6.1, 6.3, 6.4, 6.5, 6.6
Week 12   No classes Exam week (repair from Block 2) No new material
Week 13 Mar 29 10.00-11.00: Homework exam questions in lecture room No new material Presence of TA
Mar 31 13.15-14.15: Homework exam questions in lecture room No new material Presence of TA
Week 14 Apr 5 Arrangements Chapter 8 slides 8 Exercises: 8.2, 8.3, 8.4, 8.7, 8.8, 8.12, 8.15, 8.16 Hand in homework exam 2
Apr 7 Delaunay triangulations Chapter 9 slides 9 Exercises: 9.2, 9.11, 9.12, 9.13, 9.16
Week 15 Apr 12 Graph drawing; Master projects See below
Apr 14 Exam practice Exercises
Week 16 Apr 21 (Thursday) Final Exam, 17.00-20.00 EDUC-BETA

Exam subject matter

The final exam is about everything in Chapters 1-9, with the exception of sections: 4.5, 4.6, 6.4, 9.5 and the Notes and Comments sections, and Section 10.1 from Chapter 10. All slides are also part of the exam subject matter (please note the extra slides below), as well as all exercises listed above. You may not use the textbook, nor your notes, nor the lecture slide copies during the exam.

The extra presentations given at the end are semi-exam material. What I mean by that is that you do not have to learn any details like running times, or know precisely how the techniques work. Some global knowledge of these presentations, by going through them twice, should suffice as the exam preparation.

Generating Realistic Terrains.
Building Generalization.
Time-Space Maps.
Proportional Symbol Maps.
Quality Ratios in Graph Drawing.
Connecting the Dots.

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.


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 with a 4 or lower, then you need a re-take. The grade for the final exam can be replaced by the grade for the re-take, early 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.

Previous exams

Some exams concerned slightly deviating material.

Exam of 2015.
Exam of 2014.
Exam of 2013.
Exam of 2012.
Exam of 2011.


Please fill in the standard questionaire for students to give feedback on the course.