Computational Geometry

i. d. R. angeboten alle 2 Semester

• Kenntnis und Beherrschung einiger wichtiger Algorithmen und Datenstrukturen in der algorithmischen Geometrie.
• Kenntnis und Verständnis einiger typischer Arten der Beweisführung in der algorithmischen Geometrie, um die Korrektheit und die Komplexität der Algorithmen und Datenstrukturen zu zeigen.
• Zahlreicher exemplarische Anwendungen dieser Algorithmen, insbesondere in der Computergraphik, aber auch in anderen Gebieten.
• Tieferes Verständnis für die Gründe, warum diese dadurch sehr effizient werden.

• Quadtrees / Octrees, Texturkompression, Isosurfaces, Terrain-Visualisierung.
• KD-trees, BSP-Trees, Boolesche Operationen auf Objekten, Textursynthese, Bounding-Volumen-Hierarchien.
• Kinetische Datenstrukturen, Collision Detection.
• Konvexe Hülle und deren Anwendungen.
• Voronoi- und Delaunay-Diagramme, Plazierungsprobleme, Approximation des Traveling Salesman Problems.
• Range-Tree und Priority-Search-Tree, Range Queries auf dem Gitter.

Bemerkung: die genaue Zusammenstellung der Themen wird jedesmal ein wenig variiert bzw. erweitert.

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

• 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)