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
- Maike Buchin, IB 3/151
- Bernhard Kilgus, IB 3/149