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
E-mail
f <dot> staals <at> uu <dot> nl

Latest News

2018-12-07 new

Here are some quick additional notes on the analysis of the point location data structure (trapezoidal) decomposition.

2018-12-05 new

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, 10.10
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 16 Deadline HW Exam 2
Fri 18 Jan Implementation + Research Projects
04 Wed 23 Jan Exam Practice Results HW Exam 2 Available
Fri 25 Jan
05 Wed 30 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 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:

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.