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