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