Die Studierenden erwerben ein systematisches Verständnis von Fragestellungen und Lösungsansätzen im Bereich der algorithmischen Geometrie, das auf dem bestehenden Wissen in der Theoretischen Informatik und Algorithmik aufbaut. Nach erfolgreicher Teilnahme an der Lehrveranstaltung können die Studierenden

• Begriffe, Strukturen und grundlegende Problemdefinitionen aus der Vorlesung erklären;
• geometrische Algorithmen exemplarisch ausführen, mathematisch präzise analysieren und ihre Eigenschaften beweisen;
• auswählen, welche Algorithmen und Datenstrukturen zur Lösung eines gegebenen geometrischen Problems geeignet sind und diese ggf. einer konkreten Problemstellung anpassen;
• unbekannte geometrische Probleme analysieren, auf den algorithmischen Kern reduzieren und daraus ein abstraktes Modell erstellen; auf Basis der in der Vorlesung erlernten Konzepte und Techniken eigene Lösungen in diesem Modell entwerfen, analysieren und die Eigenschaften beweisen.

Räumliche Daten werden in den unterschiedlichsten Bereichen der Informatik verarbeitet, z.B. in Computergrafik und Visualisierung, in geographischen Informationssystemen, in der Robotik usw. Die algorithmische Geometrie beschäftigt sich mit dem Entwurf und der Analyse geometrischer Algorithmen und Datenstrukturen. In diesem Modul werden häufig verwendete Techniken und Konzepte der algorithmischen Geometrie vorgestellt und anhand ausgewählter und anwendungsbezogener Fragestellungen vertieft. Konkrete Vorlesungsthemen sind Algorithmen und Datenstrukturen für:

• konvexe Hülle
• Linienschnitte
• Polygontriangulierung
• Bereichsabfragen
• Punktlokalisierung
• Voronoi-Diagramme und Delaunay-Triangulierungen
• Dualität von Punkten und Geraden
• Quadtrees
• Well-Separated Pair Decomposition

ECTS-Breakdown

25 h Vorlesung
20 h Nachbereitung der Vorlesung und vorbereiten der Übungen
  5 h Präsentation der Übungen
24 h Prüfungsvorbereitung
  1 h Mündliche Prüfung
------
75 h gesamt 

Allgemeine und organisatorische Fragen bitte an alggeom-ws15@ac.tuwien.ac.at.

Dozent der Vorlesung ist: Martin Nöllenburg

Aktive Teilnahme an den Übungen ist erforderlich. Die abschließende Prüfung ist mündlich.

Vortragsfolien bzw. Artikel zu bestimmten Themen werden in der Vorlesung kostenlos verteilt und/oder zum Download angeboten.

Empfohlene Literatur:

M. de Berg, O. Cheong, M. van Kreveld, M. Overmars:
Computational Geometry Algorithms and Applications, Springer 2008.

D. Mount:
CMSC 754 Computational Geometry Lecture Notes, U. Maryland 2014.

Grundkenntnisse in Entwurf und Analyse von Algorithmen

Vorlesungsfolien werden zur Verfügung gestellt