Geometric Algorithms (INFOGA) 2018, 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.
During the course we will study various algorithmic techniques and geometric concepts that are useful to solve geometric problems efficiently. These include plane sweep, randomized incremental construction, and multi-level data structures; geometric concepts include Voronoi diagrams and Delaunay triangulations, arrangements, and duality. We will apply these techniques to solve a variety of problems: convex-hull computation, line-segment intersection, polygon triangulation, low-dimensional linear programming, range searching, and point location are some examples. Each problem we study is motivated by a practical problem from one of the application areas.
- Lecturer
- Frank Staals
- f <dot> staals <at> uu <dot> nl
Latest News
2019-03-06 new
The Retake Homework Exam is now available. The deadline for handing in your solutions (nicely typesetted, on paper) is 22 March, 23:59. You can find the LaTeX sources here.
2019-02-20
For most the course is over now. For those who wish to do the retake homework exam: it will be made available on March 6, and has to be handed in by March 22 (on paper in my office BBG 4.15). The retake for the final exam is on April 17. I’ve added those dates to the schedule below.
2019-01-23
I’ve added some more details on what material will be part of the final exam. See the bottom of the page. Note that the exam is closed book: you cannot use the book, notes, or slides during the exam.
2019-01-18
I’ve added my solutions for the questions from Homework Exam 2. Once again, keep in mind that these are mostly just sketches on how to solve the exercises.
Furthermore, I’ve added the slides about potential master topics. See the schedule below. I’ve also added the slides that I had prepared (but did not present).
2018-12-21
Homework Exam 2 is now available. The deadline for handing in your solutions (nicely typesetted, on paper) is 16 January, 15:00 (the end of our class that day). You can find the LaTeX sources here.
Morever, here are my solutions for the questions from Homework Exam 1. Keep in mind that 1) they are short on figures, and 2) in they are somewhat terse in some parts. For the most part they give a reasonable indication of the level of detail I would expect though.
2018-12-19
Some of you asked for the tex-source file for the homework assignment. Here it is.
2018-12-18
I just updated the slides corresponding to the Windowing lecture for tomorrow. We are covering a slightly different set of results compared to the slides as they were posted originally.
2018-12-07
Here are some quick additional notes on the analysis of the point location data structure (trapezoidal) decomposition.
2018-12-05
Homework Exam 1 is now available. The deadline for handing in your solutions (nicely typesetted, on paper) is 21 December, 11:00 (the end of our class that day).
2018-11-07
Updated the schedule to account for a missing lecture.
2018-10-24
The website is online.
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 14 Nov | Introduction + Convex hull | 1 | 1.3, 1.6a, 1.7a-d, 1.9 | |
Fri 16 Nov | |||||
47 | Wed 21 Nov | Line segment Intreserction | 2 | 2.2, 2.3, 2.11, 2.12 | |
Fri 23 Nov | Map Overlay | 2 | 2.5-8, 2.13, 2.14 | ||
48 | Wed 28 Nov | Polygon Triangulation | 3 | 3.3, 3.4, 3.9, 3.12, 3.14 | |
Fri 30 Nov | Linear Programming | 4 | 4.1, 4.3, 4.7 | ||
49 | Wed 5 Dec | Smallest Enclosing Disk | 4 | 4.10, 4.12, 4.14 | HW 1 Distributed |
Fri 7 Dec | Point Location | 6 | 6.1, 6.3, 6.4, 6.5, 6.6 | notes on the analysis | |
50 | Wed 12 Dec | Range Searching (KD-Trees) | 5 | 5.1, 5.2, 5.5 | |
Fri 14 Dec | Range Searching (Range Trees) | 5 | 5.7, 5.8, 5.10, 5.11, 5.12 | ||
51 | Wed 19 Dec | Windowing Queries | 10 | 10.1, 10.9 | Some Additional slides |
Fri 21 Dec | Voronoi Diagrams | 7 | 7.1, 7.5, 7.7, 7.10, 7.11 | Deadline HW Exam 1, HW 2 Distributed | |
52 | Christmas + New Year | ||||
01 | |||||
02 | Wed 09 Jan | Delaunay Triangulations | 9 | 9.2, 9.11, 9.12, 9.13, 9.16 | Results HW 1 Available |
Fri 11 Jan | Arrangements | 8 | 8.2, 8.3, 8.4, 8.7, 8.8, 8.12, 8.15, 8.16 | ||
03 | Wed 16 Jan | Simplex Range Searching 1 and 2 | 16 | Deadline HW Exam 2 | |
Fri 18 Jan | Implementation + Research Projects | Master Projects Marc, Maarten, Frank | |||
04 | Wed 23 Jan | Exam Practice | Results HW Exam 2 Available | ||
Fri 25 Jan | – | ||||
05 | Wed 30 Jan | Final Exam | |||
… | |||||
Wed 06 Mar | Retake HW Distributed | ||||
Fri 22 Mar | Deadline Retake HW Exam | ||||
16 | Wed 17 Apr | 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 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. 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.
Homework Exams (2 x 25%)
There are two 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).
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,16 of the book (with the exception of Sections 4.5, 4.6, 6.4, 7.3, 7.4, 9.5, 10.2, 16.1,16.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.
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 last year..
Feedback
Please fill in the standard questionnaire for students to give feedback on the course.