Geometrische Algorithmen umfasssen den Entwurf und die Analyse von Algorithmen und Datenstrukturen für geometrische Probleme. In der Vorlesung werden zunächst einige grundlegende Probleme betrachtet: Das Berechnen der konvexen Hülle einer Punktmenge, der Schnittpunkte einer Menge von Strecken, oder einer Triangulierung eines einfachen Polygons. Anschließend sehen wir Algorithmen zum Berechnen bekannter geometrische Strukturen, wie Voronoi-Diagramme, Delaunay-Triangulierungen und Arrangements. Ebenfalls betrachten wir Datenstrukturen für effiziente Anfragen auf geometrischen Daten, wie Range-trees, kd-Bäume und Quadtrees. Dabei kommen vor allem drei Arten von Algorithmen zum Einsatz: inkrementell, teile-und-herrsche, und sweep. Manche von diesen treten als randomisierte Algorithmen auf.
Als Vorkenntnisse wird die Vorlesung “Algorithmen und Datenstrukturen” oder vergleichbare Kenntnisse erwartet.