Geometric Algorithms (INFOGA) 2024-2025, 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.

Latest News

2025-02-12

The Retake HW is Available. Here is also it’s source file.

2024-12-11

HW 3 is Available. Here is also it’s source file.

2024-11-29

Here is my model solution to HW 1.

2024-11-22

HW 2 is Available. Here is also it’s source file.

2024-11-12

HW 1 is Available. Here is also it’s source file.

2024-10-30

Updated website for 2024.

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 13 Nov	1	1.3, 1.6a, 1.7a-d, 1.9	HW 1 is Available
	Line segment Intreserction	Fri 15 Nov	2	2.2, 2.3, 2.11, 2.12
47	Map Overlay	Wed 20 Nov	2	2.5-8, 2.13, 2.14
	Polygon Triangulation	Fri 22 Nov	3	3.3, 3.4, 3.9, 3.12, 3.14	Deadline HW Exam 1, HW 2 Distributed
48	Linear Programming	Wed 27 Nov	4	4.1, 4.3, 4.7
	Discuss HW1 + Work on HW2	Fri 29 Nov
49	Smallest Enclosing Disk	Wed 4 Dec	4	4.10, 4.12, 4.14	Results HW 1 Available
	Point Location	Fri 6 Dec	6	6.1, 6.3, 6.4, 6.5, 6.6	notes on the analysis
50	Range Searching (KD-Trees)	Wed 11 Dec	5	5.1, 5.2, 5.5	Deadline HW Exam 2, HW3 Distributed
	Range Searching (Range Trees)	Fri 13 Dec	5	5.7, 5.8, 5.10, 5.11, 5.12	Range Searching Overview
51	Voronoi Diagrams	Wed 18 Dec	7	7.1, 7.5, 7.7, 7.10, 7.11
	Discuss HW2	Fri 20 Dec
52	Christmas + New Year				Results HW 2 Available
01
02	Delaunay Triangulations	Wed 08 Jan	9	9.2, 9.11, 9.12, 9.13, 9.16
	Arrangements	Fri 10 Jan	8	8.2, 8.3, 8.4, 8.7, 8.8, 8.12, 8.15, 8.16
03	Windowing Queries	Wed 15 Jan	10	10.1, 10.9	Deadline HW Exam 3
	Q&A + Exam Practice	Fri 17 Jan
04	Discuss HW3 + Research Projects	Wed 22 Jan			Results HW Exam 3 Available
	–	Fri 24 Jan			Deadline Bonus Project
05	Final Exam	Wed 29 Jan
08		Wed 19 Feb			Retake HW Available
12		Wed 19 Mar			Deadline Retake HW
16	Retake Exam	Wed 16 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 (1x5%, 2 x 25%)

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 45%)

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.

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.