Geometrische Algorithmen SS 2023

LVR-Nr: 211043
Veranstaltung: Geometrische Algorithmen
2-std.
Fr, 12-14 Uhr
Dozentin: Maike Buchin
Übungen: Christoph Ries
Korrektur: t.b.a.

Aktuelles

  • Alle weiteren Informationen sind dem Moodlekurs zu entnehmen.

 

Informationen

Kommentar aus dem Vorlesungsverzeichnis

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.

Voraussetzungen

Grundlegende Vorlesung zu Algorithmen und Datenstrukturen, wie zum Beispiel die Informatik 2.

Literatur

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).

Weitere Literaturhinweise werden in der Vorlesung gegeben.

Kontakt