| NUMMER: | 150341 |
| KÜRZEL: | GeoAlg |
| MODULBEAUFTRAGTE:R: | Prof. Dr. Buchin Maike |
| DOZENT:IN: | Prof. Dr. Maike Buchin |
| FAKULTÄT: | Fakultät für Informatik |
| SPRACHE: | Deutsch |
| SWS: | 6 SWS |
| CREDITS: | 6 CP |
| ANGEBOTEN IM: | jedes Wintersemester |
PRÜFUNGEN
| FORM: | mündlich |
| TERMIN: | Siehe Prüfungsamt. |
LERNFORM
Vorlesung als kombinierter Folien- und Tafelvortrag, Übungen mit begleitendem Implementierungsprojekt
LERNZIELE
Nach dem erfolgreichen Abschluss des Moduls∙ kennen Studierende grundlegende geometrische Algorithmen und Datenstrukturen
∙ können Studierende Algorithmen nach dem Sweep-Paradigma analysieren und entwerfen
∙ können Studierende inkrementelle Algorithmen entwerfen und analysieren, insbesondere
randomisiert inkrementelle Algorithmen
∙ können Studierende geometrische Algorithmen nach dem Teile-und-Herrsche Prinzip
analysieren und entwerfen
∙ können Studierende für Bereichsanfragen geeignete Datenstrukturen aussuchen
INHALT
Die Algorithmische Geometrie beschäftigt sich mit dem Entwurf und der Analyse von Algorithmenund Datenstrukturen für geometrische Probleme. Dazu werden zunächst einige
grundlegende Probleme betrachtet, wie 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 das Voronoi-Diagramm, die Delaunay-Triangulierung und Arrangements. Ebenfalls
betrachten wir Datenstrukturen für effiziente Anfragen auf geometrischen Daten, wie Rangetrees,
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 CREDITS
Bestandene mündliche Prüfung, sowie als Studienleistung erfolgreiches Bearbeiten der Übungenund des Projektes mit Abgabe eines Projektberichtes
EMPFOHLENE VORKENNTNISSE
Grundlagen der Stochastik.
LITERATUR
Die Vorlesung orientiert sich groesstenteils an dem Buch "Computational Geometry:Algorithms and Applications", von Mark de Berg, Otfried Cheong, Marc van Kreveld,
und Mark Overmars (3te Auflage, 2008, Springer).