# 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

Date | Topic | Lecturer/Tutor | Slides/Assignment |
---|---|---|---|

05.05 | Introduction - Arrangements, duality, outlook | Raimund Seidel | |

07.05 | Convex hulls in the plane | Sándor Kisfaludi-Bak | |

12.05 | 3-dimensional convex hulls | Sándor Kisfaludi-Bak | |

14.05 | Tutorial 1 | André Nusser | |

19.05 | Low-dimensional linear programming | Raimund Seidel | |

21.05 | Orthogonal range searching | Sándor Kisfaludi-Bak | |

26.05 | Line segment intersections, segment trees | Raimund Seidel | |

28.05 | Tutorial 2 | André Nusser | |

02.06 | Point Location | Raimund Seidel | |

04.06 | Voronoi diagrams, Delaunay triangulations | Sándor Kisfaludi-Bak | |

09.06 | Quadtrees, compressed quadtrees | Raimund Seidel | |

Tutorial 3 | André Nusser | ||

16.06 | Well-separated pair decomposition, spanners | Raimund Seidel | |

18.06 | Clustering, k-center, k-median | Sándor Kisfaludi-Bak | |

23.06 | Planar separator, shifting for packing and covering | Sándor Kisfaludi-Bak | |

25.06 | Tutorial 4 | André Nusser | |

30.06 | Range spaces, VC dimension | Raimund Seidel | |

02.07 | Coresets | Sándor Kisfaludi-Bak | |

07.07 | Hitting set and set cover via local search | Sándor Kisfaludi-Bak | |

09.07 | Tutorial 5 | André Nusser | |

14.07 | Configuration spaces | Raimund 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.)