Geometric Algorithms (INFOGA)

Year 2016/2017, block 4: April-June 2017

Lecturers

News

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 Chapters 1-10, along with some other topics.

Schedule (tentative)

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
Extra session:
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
Extra session:
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
(Location: ANDRO-C138)
Chapter 8 slides 8
+ Extras
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
Section 10.3)
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
(Tuesday)
Final Exam, 13.30-16.30
EDUC-MEGARON

Final exam material

The subject matter for the final exam consists of the following:

You may not use the textbook, nor your notes, nor the lecture slide copies during the exam.

Extras

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.

Grading

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.

Previous exams

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.

Feedback

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