Geometric Algorithms (INFOGA) 2019, 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
- 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
2020-03-17 new
Since all teaching activities, including exams, are suspended until at least April 20, that also means that the Re-take exam for Geometric Algorithms, originally scheduled for April 15th, is canceled. More specifically, we will have to postpone the Re-take until a later date. Unfortunately, I do not know yet when the exam will/can take place. More information will follow.
2020-03-12 new
Due to all of the anti-corona measures you are now allowed to hand in your retake-homework exam by email as well. The deadline is still March 13 17:00 (tomorrow).
2020-02-28
Here is the retake homework exam (and it’s tex file). The deadline is March 13 17:00.
2020-02-20
I’ve added the Retake Homework Exam and the Retake Exam to the schedule. The Homework Exam will be released on Friday 28 February. The deadline is March 13 17:00. Make sure to hand in your solutions on paper at my office (BBG 4.11).
The retake exam is on Wednesday April 15.
2020-02-14 new
I just entered the grades in Osiris. If you want to have a look at your exam, feel free to drop by my office.
For those that have an ‘AANV’ you will have to do the retake homework exam and/or retake the final exam. I will send out an email with the details early next week.
Also for those students that participated in the bonus assignment, I’ll send you guys an email with some details and feedback early next week.
I hope you guys learned a lot and enjoyed the course!
2020-01-24
For those that passed only two out of the three homework exams there will be a retake homework exam in block three. I will send more information about that by email.
The final Exam is next week, Wednesday 29 January from 17:00 to 20:00. According to Osiris the exam will take place in Educ Gamma.
Good luck!
2019-12-11
I’ve updated the formulation of question 2 of Homework Exam 3. In particular, I’ve clarified that your data structure should support a sublinear query time.
Furthermore, you should have received an email with your score for the second homework exam. I will wring your solutions to the next lecture, but if you want to have a look at them before that please drop by my office.
2019-12-11
Homework Exam 3 is available (here is the LaTeX source.
2019-12-03
As promised, I fixed the issue in my writeup of the solution to Homework Exam 1. Changes are highlighted in red.
Moreover, the details of the bonus assignment are now available. Please let me know if you are planning on making the bonus assignment by December 18th (the last lecture before the Christmas holiday).
2019-11-13
Homework Exam 2 is available (here is the LaTeX source.
Furthermore, here is a writeup of the solution to Homework Exam 1. Hopefully, this gives you some rough indication of the expected level of detail. However, note that, for one, this writeup misses figures!
2019-11-13
Homework Exam 1 is available. The LaTeX source is also available.
2019-11-05
Updated website for 2019
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 14 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 | |
Smallest Enclosing Disk | Fri 29 Nov | 4 | 4.10, 4.12, 4.14 | Results HW 1 Available | |
49 | Point Location | Wed 4 Dec | 6 | 6.1, 6.3, 6.4, 6.5, 6.6 | notes on the analysis |
Range Searching (KD-Trees) | Fri 6 Dec | 5 | 5.1, 5.2, 5.5 | ||
50 | Range Searching (Range Trees) | Wed 11 Dec | 5 | 5.7, 5.8, 5.10, 5.11, 5.12 | Deadline HW Exam 2, HW 3 Distributed |
Voronoi Diagrams | Fri 13 Dec | 7 | 7.1, 7.5, 7.7, 7.10, 7.11 | ||
51 | Arrangements + Discuss HW2 | Wed 18 Dec | 8 | 8.2, 8.3, 8.4, 8.7, 8.8 | Results HW 2 Available |
– | Fri 20 Dec | ||||
52 | Christmas + New Year | ||||
01 | |||||
02 | Arrangements (Part 2) | Wed 09 Jan | 8.12, 8.15, 8.16 | ||
Delaunay Triangulations | Fri 10 Jan | 9 | 9.2, 9.11, 9.12, 9.13, 9.16 | Deadline HW Exam 3 | |
03 | Windowing Queries | Wed 15 Jan | 10 | 10.1, 10.9 | |
Discuss HW3 + Research Projects | Fri 17 Jan | ||||
04 | Q&A + Exam Practice | Wed 22 Jan | Results HW Exam 3 Available | ||
– | Fri 24 Jan | Deadline Bonus Project | |||
05 | Final Exam | Wed 29 Jan | |||
09 | Fri 28 Feb | Retake HW Available | |||
11 | Fri 13 Mar | Deadline Retake HW: 17:00 | |||
16 | |||||
?? | Retake Exam | ?? |
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, 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, before the end 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, i.e. including those of the “Implementation” lecture.
- 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.
- Exam of 2018
- Exam of 2015
- Exam of 2014
- Exam of 2013
- Exam of 2012
- Exam of 2011
- Exam of 2009
- Exam of 2008
Here are also examples of the homework exams from last year.
- Homework Exam 1 of 2018 and the solutions
- Homework Exam 2 of 2018 and the solutions
- Homework Exam 1 of 2017
- Homework Exam 2 of 2017
Feedback
Please fill in the standard questionnaire for students to give feedback on the course.