Studierende lernen eine Reihe von fundamentalen Datenstrukturen (und zugehörige Algorithmen) aus dem Gebiet der Computational Geometry kennen. Darüber hinaus lernen Sie, diese auf Probleme der Computergraphik anzuwenden und kreativ damit umzugehen. Weiterhin lernen Studenten, etwas aufwendigere Komplexitätsanalysen über geometrische Algorithmen zu führen.

Wo sollte man ein neues Haus plazieren, damit es möglichst weit von Störquellen entfernt ist? Wie sollte man Punkte in einem Höhenfeld verbinden, damit ein möglichst “plausibles” 3D Terrainmodell entsteht? Wie kann man Bilder möglichst einfach aber dennoch platzsparend speichern oder übertragen? (JPEG ist zwar platzsparend, aber nicht besonders einfach)

Bei vielen Algorithmen, insbesondere auch in der Computer-Graphik, liegt das Geheimnis ihrer Effizienz in den jeweils verwendeten geometrischen Datenstrukturen. In dieser Vorlesung sollen verschiedene solche Datenstrukturen besprochen werden, die sich in der Praxis als sehr erfolgreich erwiesen haben. Bevorzugt werden diejenigen Datenstrukturen und Algorithmen angesprochen, die sowohl universell einsetzbar als auch relativ einfach zu implementieren sind.

Zu allen Datenstrukturen werden einige Algorithmen, vorzugsweise, aber nicht ausschließlich aus der Computer-Graphik, vorgestellt, die deren Verwendung demonstrieren.

Geplante Themen:

• Quadtrees / Octrees, Texturkompression, Isosurfaces, Terrain-Visualisierung,
• kd-trees, BSP-Trees, Boolesche Operationen, Textursynthese, Bounding-Volumen-Hierarchien,
• Kinetische Datenstrukturen, Collision Detection, Konvexe Hülle,
• Voronoi- und Delaunay-Diagramme, Plazierungsprobleme, Approximatoin des TSP,
• Range-Tree und Priority-Search-Tree, Range Queries auf dem Gitter

Achtung: dieser Themen-Mix wird meistens jedesmal etwas variiert.

Die Vorlesung bewegt sich an der Schnittstelle zwischen Computational Geometry und Computer-Graphik. Daher werden keine praktischen sondern nur (einfache) theoretische Übungsaufgaben gestellt werden.

i.d.R. Bearbeitung von Übungsaufgaben und Fachgespräch oder mündliche Prüfung

• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications; Springer;
• Franco P. Preparata, Michael Ian Shamos: Computational Geometry: An Introduction; Springer (schon etwas älter, aber immer noch ein Klassiker);
• Rolf Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen; Springer;
• Joseph O’Rourke: Computational Geometry in C. Cambridge University Press;
• G. Zachmann & E. Langetepe: Geometric Data Structures for Computer Graphics, CRC Press, 2006, ISBN: 9781568812359 (ehemals AK Peters).