- Marc van Kreveld (M.J.vanKreveld@uu.nl)
- Wouter van Toll (W.G.vanToll@uu.nl)

- (June 21, 2017)
- The grades for homework exam 2 are available.
- Some answers and notes are available as well.
- Tomorrow, we will hand out your graded work with comments.
- Remember: if one of the two grades is lower than 5 (shaded in the PDF), you can still pass the course if you pass a retake homework exam. See the "Grading" section below for more details.

- (June 20, 2017) The slides of today's "Implementation" lecture are now online (see schedule).
- (June 12, 2017) Thursday's lecture will be about the first parts of Chapter 10. The schedule and exam material have been updated.
- (June 8, 2017) We've updated the schedule for the remainder of the course, as well as the final exam material. Any material marked as "TBA" will be added as soon as possible.
- (June 1, 2017) Homework exam 2 distributed. If anything is unclear, please let us know.
- (May 31, 2017)
- The grades for homework exam 1 are available.
- Some answers and notes are available as well.
- Tomorrow, we will hand out your graded work with comments.

- (May 10, 2017) Homework exam 1 distributed.
- (April 25, 2017) The two homework exam Q&A sessions will take place in BBG 0.05,
*after*a regular Tuesday lecture. See the schedule below. - (April 24, 2017) There will be two extra sessions in which you can ask questions about the homework exam (if you want to). These sessions will most likely take place on Tuesday afternoons; the exact times and locations are still pending.
- (April 13, 2017) First update of the web page, with tentative schedule.

This page is still under construction. Click here to visit last year's website.

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 | |

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.30EDUC-MEGARON |

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

- everything in Chapters 1-10 of the book (with the exception of Sections 4.5, 4.6, 6.4, 9.5, 10.3, and the Notes and Comments sections);
- all slides downloadable from the schedule, i.e. including those of the "Implementation" lecture, but excluding the "Extras" below;
- all exercises from the book listed in the schedule.

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.

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

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.