Geometrische Algorithmen

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 Algorithmen
und 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 Übungen
und 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).

AKTUELLE INFORMATIONEN

Die Veranstaltung entfällt im WS 22/23