RUB » LMI » Lehre » Algorithmische Geometrie WS19/20

Algorithmische Geometrie Winter 2019/2020

LVR-Nr: 150 362
Veranstaltung: Algorithmische Geometrie
2 std.
IA 1/135 Do 10:00-12:00
Dozentin: Maike Buchin
Übungen: Bernhard Kilgus
2 Std., alle zwei Wochen
IA 1/135 Fr 12.00 - 14.00
Die erste Übung findet am 25.10. statt.

News

  • Die Vorlesung am Donnerstag, den 30.1. entfällt.

Kommentar

Die Algorithmische Geometrie beschäftigt sich mit dem Entwurf und der 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üfungsleistung zum Modul Algorithmische Geometrie ist in Form einer mündlichen Prüfung zu erbringen.

Die Prüfungsanmeldung erfolgt nach den Regeln des für Sie zuständigen Prüfungsamtes.

Für mündlichen Prüfungen stehen Termine am Di, den 11.2. und voraussichtlich am Di, den 31.3. zur Verfügung. Bitte lassen Sie sich vor der Anmeldung zur Prüfung eine Uhrzeit von Bernhard Kilgus geben.

Kontakt