RUB » LMI » Lehre » Geometrische Algorithmen WS21/22

Geometrische Algorithmen Winter 2021/2022

LVR-Nr: 150 362
Veranstaltung: Geometrische Algorithmen
2 std.
online in Zoom Di 8:30-10:00
Dozentin: Maike Buchin
Übungen: Alexander Neuhaus
online in Zoom Di 14.15 - 15.45
Die erste Übung findet am 19.10. statt.

News

  • Aufgrund der aktuellen Situation wird die Vorlesung ausschließlich online stattfinden. Bitte tragen Sie sich hierfür in den Moodle-Kurs ein.

Kommentar

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

Es werden grundlegende Kenntnisse über Algorithmen und Datenstrukturen erwartet, sowie grundlegende Kenntnisse der Stochastik.

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

Materialien

Die Materialien werden im zugehörigen Moodle-Kurs veröffentlicht werden.

Prüfungen

Die Prüfungsmodalitäten werden in der ersten Vorlesung bekannt gegeben.

Kontakt