Computational Geometry

Advanced Course, 3+1

Basic Information

Lectures:Tuesday 10:00-12:00, Odd week Thursday 10:00-12:00  Location:Zoom, see below
Lecturers:Raimund Seidel and Sándor Kisfaludi-Bak
First lecture:May 5. 10:15 AM
Tutorials:Even week Thursday 10:00-12:00
Assistant:André Nusser
First tutorial:May 14. 10:15 AM
Credits:6
Exam:Take-home (can be done virtually)
Prerequisites:Basics of data structures, algorithms, computational complexity, and linear algebra

Announcements

All students should subscribe to the mailing list at https://lists.mpi-inf.mpg.de/listinfo/compgeo20

Zoom URL: https://zoom.us/j/99444908708
If you still need the password for the lectures and tutorials, please send us an email.

Description

Computational geometry considers problems with geometric input, and its goal is to design efficient algorithms and to study the computational complexity of such problems. A typical input to a problem is some set of points or segments in the Euclidean plane (or higher dimensional Euclidean space). Examples of problems include computing the convex hull of the point set, finding clusters, or setting up a data structure to find the nearest point to a given query point. Although not the focus of this course, there is a very rich application domain, including computer graphics, computer-aided design and manufacturing, machine learning, robotics, geographic information systems, computer vision, integrated circuit design, and many other fields.

 

The course introduces the most important tools used in the design of computational geomtric algorithms. The larger part of the course will deal with problems that can be solved exacly in near-linear time, which are practically solvable even on very large inputs. Towards the end we will deal with hard (often NP-hard) problems, and see some tools that help in creating approximation algorithms.

 

Schedule

DateTopicLecturer/TutorSlides/Assignment
05.05Introduction - Arrangements, duality, outlookRaimund Seidelpdf
07.05Convex hulls in the planeSándor Kisfaludi-Bakpdf
12.053-dimensional convex hullsSándor Kisfaludi-Bakpdf
14.05Tutorial 1André Nusserpdf
19.05Low-dimensional linear programmingRaimund Seidelpdf
21.05Orthogonal range searchingSándor Kisfaludi-Bakpdf
26.05Line segment intersections, segment treesRaimund Seidelpdf
28.05Tutorial 2André Nusserpdf
02.06Point LocationRaimund Seidelpdf
04.06Voronoi diagrams, Delaunay triangulationsSándor Kisfaludi-Bakpdf
09.06Quadtrees, compressed quadtreesRaimund Seidelpdf
11.06 16.06, 12:15Tutorial 3André Nusserpdf
16.06Well-separated pair decomposition, spannersRaimund Seidelpdf
18.06Clustering, k-center, k-medianSándor Kisfaludi-Bakpdf
23.06Planar separator, shifting for packing and coveringSándor Kisfaludi-Bakpdf
25.06Tutorial 4André Nusserpdf
30.06Range spaces, VC dimensionRaimund Seidelpdf
02.07CoresetsSándor Kisfaludi-Bakpdf
07.07Hitting set and set cover via local searchSándor Kisfaludi-Bakpdf
09.07Tutorial 5André Nusserpdf
14.07Configuration spacesRaimund Seidel 
16.07

Dimension reduction, metric embeddings

Sándor Kisfaludi-Bak 

Material

  • Some of the lectures will have significant overlaps with chapters of the "Dutch book":
    Computational Geometry: Algorithms and Applications (3rd edition) by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.
    See here.
  • Towards the end of the semester, we will have some overlap with the following book:
    Geometric Approximation Algorithms by Sariel Har-Peled.
    See here and here. (Note that the published book has much better and much more content than what is available on the author's webpage.)