Computational Geometry (211056-SoSe 2025)

Computational Geometry deals with the design and analysis of algorithms and data structures for geometric problems. To this end, we first look at some basic problems, such as calculating the convex hull of a set of points, the intersection points of a set of line segments, or a triangulation of a simple polygon. We then look at algorithms for calculating well-known geometric structures such as Voronoi diagrams, Delaunay triangulations and arrangements. We also look at data structures for efficient queries on geometric data, such as Range Trees, kd-Trees and Quadtrees. Three main types of algorithms are used: incremental, divide-and-conquer, and sweep. Some of these occur as randomized algorithms.