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.

• Vorlesung + Übung
  • Montag, 10:15-12:00 Uhr, OH 14 Raum 104, Vorlesung
  • Mittwoch, 10:15-12:00 Uhr, OH 14 Raum 104, Übung
• Beginn der Vorlesungen: tba

• Prüfungen (s. Modulbeschreibung sowie Folien der ersten Vorlesung):
  • mündlich
  • aktive Teilnahme (inkl. Präsentation eigener Lösungen)

• Vorlesungsfolien
• Die Vorlesung orientiert sich im Wesentlichen an dem Buch “Computational Geometry: Algorithms and Applications”, von Mark de Berg, Otfried Cheong, Marc van Kreveld, und Mark Overmars (3. Auflage, 2008, Springer).