Die Vorlesung beschäftigt sich mit dem Entwurf und der
Analyse von Algorithmen und Datenstrukturen für geometrische Probleme.
Dazu 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.
- Kursleiter/in: Maike Buchin
- Kursleiter/in: Bernhard Helmut Kilgus
- Kursleiter/in: Leonie Ryvkin