Geometric Algorithms (INFOGA) 2025-2026, Block 2

In many areas of computer science it is necessary to store, analyze, and create or manipulate spatial data. Examples are robotics, computer graphics and virtual reality, and geographic information systems. This course deals with the algorithmic aspects of these tasks: we study the design and analysis of geometric algorithms and data structures.

Lecturer: Frank Staals
E-mail: f <dot> staals <at> uu <dot> nl

Learning Objectives

After following this course you are able to design provably correct and efficient algorithms to solve basic geometric problems. To this end, you can apply algorithmic techniques such as

plane sweep,
randomized incremental construction,
multi-level data structures, and
duality,

and use concepts such as

Voronoi diagrams
Delaunay triangulations, and
Arrangements.

Schedule

Here is the schedule for this years course. Keep in mind that it is subject to change.

Week	Topic	Date	Book Chapter	Exercices	Notes
46	Introduction + Convex hull	Wed 12 Nov	1	1.3, 1.6a, 1.7a-d, 1.9	HW 1 is Available (LaTeX file).
	Line segment Intreserction	Fri 14 Nov	2	2.2, 2.3, 2.11, 2.12
47	Map Overlay	Wed 19 Nov	2	2.5-8, 2.13, 2.14
	Polygon Triangulation	Fri 21 Nov	3	3.3, 3.4, 3.9, 3.12, 3.14	Deadline HW Exam 1, HW 2 Distributed (LaTeX file).
48	Linear Programming	Wed 26 Nov	4	4.1, 4.3, 4.7
	Discuss HW1 + Work on HW2	Fri 28 Nov			Model solution for HW1
49	Smallest Enclosing Disk	Wed 3 Dec	4	4.10, 4.12, 4.14
	Point Location	Fri 5 Dec	6	6.1, 6.3, 6.4, 6.5, 6.6	notes on the analysis, Results HW 1 Available
50	Range Searching (KD-Trees)	Wed 10 Dec	5	5.1, 5.2, 5.5	Deadline HW Exam 2, HW 3 Distributed (LaTeX file).
	Range Searching (Range Trees)	Fri 12 Dec	5	5.7, 5.8, 5.10, 5.11, 5.12	Range Searching Overview
51	Voronoi Diagrams	Wed 17 Dec	7	7.1, 7.5, 7.7, 7.10, 7.11
	Discuss HW2	Fri 19 Dec
52	Christmas + New Year				Results HW 2 Available
01
02	– No lecture due to winter weather –	Wed 07 Jan
	Delaunay Triangulations	Fri 09 Jan	9	9.2, 9.11, 9.12, 9.13, 9.16
03	Arrangements	Wed 14 Jan	8	8.2, 8.3, 8.4, 8.7, 8.8, 8.12, 8.15, 8.16	Deadline HW Exam 3
	Windowing Queries	Fri 16 Jan	10	10.1, 10.9
04	Q&A + Exam Practice	Wed 21 Jan
	Discuss HW3 + Research Projects	Fri 23 Jan			Results HW Exam 3 Available, Deadline Bonus Project
05	Final Exam	Fri 30 Jan
10		Tue 03 Mar			Retake HW Available
14		Thu 02 Apr			Deadline Retake HW
16	Retake Exam	Wed 15 Apr

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.

Grading

The final grade is based on three homework exams and one final exam. Each of these items must be graded with at least a 5, and the weighted average, rounded (according to Sec 5.4 of the OER rounding rules), must be at least a 6. In addition, there will be a bonus assignment worth 0.5pt. The maximum achievable grade is a 10. The final exam is “closed book”.

Note that the homework exams force you to actively participate in the course. You cannot just wait until the final exam.

Homework Exams (1x10%, 2 x 20%)

There are three homework exams, which you have to hand in on paper at the day of the deadline. In particular, by the beginning of the class that day (or earlier if you do not come to class). Produce a carefully prepared document with your solutions, with proper type-setting (preferably with latex), and suitable figures. Handwritten solutions are not accepted. Consider using ipe to typeset your figures (ipe was specifically created to make the figures in the book).

The first homework exam will be very small, and is meant mostly to practice how to write down the solution appropriately, that is, in a structured, concise manner. The goal of the other two homework exams is to learn how to design provably correct and efficient algorithms to solve basic geometric problems. These homework exams will be much larger than the first homework exam.

When you are asked to design an algorithm, your answer should typically (i.e. unless specified otherwise) consist of four parts:

geometric observations about the problem, ideally with proofs,
a description of the algorithm,
a proof/argument that your algorithm is correct, most likely referring to the geometric observations, and
the analysis of the running time of your algorithm.

Start on solving the questions as early as possible. Give yourself the time to think about the questions and their solutions. Be precise, correct, and succinct (but complete) in your explanations, algorithms, and running time analyses. It is essential that you spend time on careful formulations, consistent notation, succinctness. Use proper notation and terminology in your solutions, the same or similar to the notation in the book. Never change notation that was given in the assignment itself (you immediately get points subtracted for this). Adopt the style, proof detail, etc., of the textbook when answering the questions. Geometric tests or constructions with constantly many elements are written in plain text (“If p lies strictly above the line …”, or “Let p be the leftmost intersection point of circle C and line …”).

You have to make the homework exams on your own. It is allowed to discuss an approach on a high level with your class mates, however thinking about the technical details and writing down the solution must be done individually.

You do not need to search for papers with similar problems, all questions can be answered by thinking and using or modifying the methods from the textbook. You do not have to copy whole code or proofs from that book, you can simply refer to them if you need it literally. But you must then refer precisely.

Final Exam (1 x 50%)

There is a final written exam. You may not use the textbook, nor your notes, nor the lecture slide copies during the exam. 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, 7.3, 7.4, 9.5, 10.2, and the Notes and Comments sections);
all slides (from the ‘Topic’ column) downloadable from the schedule.
all exercises from the book listed in the schedule.

Bonus assignment (0.5 pt)

There will be a bonus assignment, that is worth at most 0.5 point. The main goal is to learn about the peculiarities of implementing geometric algorithms.

See the bonus page for details.

Retake options

If you do not make or fail (< 5) two or more of the homework exams, you fail the course.

If you fail one homework exam, you get a new, homework exam based on later chapters of the book to replace the failed homework. This retake homework exam will be distributed in block 3.

To qualify for the second opportunity of the final exam, you must have a grade of 5 or higher for three homework exams. The retake exam then replaces the grade for the final exam.

AI Policy

Any form of AI help in their assignments is not allowed: the AI Index for Geometric Algorithms is 1. You are expected to rely on your own understanding, reasoning ability and skills to complete the work in the course.

Previous Exams

Below are the final exams from previous years. Note that some exams concerned slightly deviating material.

Here are also examples of the homework exams from earlier years.

Feedback

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