|
|
Inhalt:
Der Inhalt der Veranstaltung ist im Wesentlichen der gleiche wie in
Computational Geometry. Die Vorlesung wird in diesem Semester jedoch auf deutsch
gehalten. In der Vorlesung wird die Algorithmische Geometrie aus dem
Blickwinkel des Algorithmenentwurfs betrachtet. Im Mittelpunkt stehen
Entwurfsparadigmen für geometrische Algorithmen, z.B.
- incremental construction
- divide and conquer
- prune and search
- plane sweep
- topological sweep
- geometric transformations
- randomization
Die Textbücher zur Algorithmischen Geometrie hingegen sind in der
Regel themenorientiert. In der Vorlesung werden unter anderem folgende
Themen behandelt:
- convex hull algorithms in 2D and 3D
- intersection of halfspaces
- Voronoi diagrams and Delaunay triangulations
Zur Vorlesung gibt es ein englischsprachiges(!) Skript. Dieses und
weitere Vorlesungsmaterialen finden Sie
hier.
Zugriff haben alle Teilnehmer an der Vorlesung.
Geben Sie als Benutzername bitte vorname.nachmane ein, also ihren Vornamen
gefolgt von einem Punkt gefolgt von ihrem Nachnamen, jeweils klein geschrieben, ohne Leerzeichen und mit expandierten Umlauten.
Aus Carl Friedrich von Weizäcker würde beispielsweise carlfriedrich.vonweizaecker. Das Kennwort ist ihre Matrikelnummer.
Übungen zur Vorlesung werden unregelmäßig angeboten und zu den
Vorlesungszeiten besprochen. Bei Interesse werden auch praktische Übungen
mit CGAL und LEDA angeboten.
Voraussetzungen:
Das in der Vorlesung Einführung in Algorithmen und Datenstrukturen
vermittelte Wissen.
Literaturempfehlung:
 |
|
 |
Mark de Berg, Marc van Kreveld,
Mark Overmars, Otfried Schwarzkopf
Computational Geometry,
Algorithms and Applications
Springer-Verlag, 2000.
|
|
Rolf Klein
Algorithmische Geometrie (2. Auflage)
Springer-Verlag, 2005.
|
|
