Die Vorlesung behandelt Themen aus der algorithmischen Geometrie. Dazu gehören zum Beispiel: Voronoi-Diagramme, algorithmische Bewegungsplanung für Roboter, Sichtbarkeit in Polygonen, konvexe Hülle, untere Kontur von Liniensegmenten und Funktionen, Sweepline-Methode und Anwendungen, geometrische Datenstrukturen: Dynamisierung, k-d-tree, Bereichsbaum, Prioritätssuchbaum.

Vorkenntnisse

Ausreichendes Verständnis von Datenstrukturen und Algorithmen (Bachelor Vorlesung).

Bachelor Modulinformationen

Algorithmen und Komplexität, V3 + Ü2 SWS, 6 ECTS Credits

Dozent

Matthias Fischer

Veranstaltungsform

Die Veranstaltung wird in Präsenz stattfinden.

Termine

• Vorlesung: siehe PAUL
• Übungen: siehe PAUL (erste Vorlesungswoche sind keine Übungen)

Prüfung

• Die Prüfungen sind mündliche Prüfungen.
• Der Inhalt umfasst alle Übungen und alle Vorlesungen.

Studienleistung

• Jede Woche erhalten Sie in PANDA einen Hausaufgabenbogen.
• Die Hausaufgaben werden in Gruppen von 2-5 Personen gelöst.
• Der Hausaufgabenbogen wird bepunktet. Für Plagiate gibt es keine Punkte. Sie müssen 30% der Punkte erreichen, um an der Prüfung teilnehmen zu können. Auf diese Weise erhalten Sie die Studienleistung.

Literatur

Algorithmische Geometrie
Rolf Klein, Springer-Verlag, 2005.
Computational Geometry: Algorithms and Applications
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Springer-Verlag, 2008
Computational Geometry
An Introduction, Franco P. Preparata; Springer, 1993
Lectures on Discrete Geomtetry
Jiri Matousek, Springer-Verlag, 2002.
Handbook of Discrete and Computational Geometry
Jacob E. Goodman, Joseph O'Rourke, CRC Press, 1997.