Algorithmische Geometrie

Beschreibung:
Obwohl einfache Schnittprobleme, z.B. zwischen Geraden in der Ebene, vom mathematischen Standpunkt aus nicht interessant sind, treten jedoch beim Schnitt von tausenden von Geraden Effizienzprobleme auf, zu deren Behandlung spezielle Algorithmen erforderlich sind. Die Entwicklung und theoretischen Analyse effizienter Algorithmen für solche Probleme mit großen Datenmengen geometrisch einfacher Objekte ist der Gegenstand der algorithmischen Geometrie. Das theoretische Interesse an solchen Fragestellungen wird durch viele praktische Anwendungen in der Computer-Graphik, im Computer Aided Design, im VLSI Design, in Robotik, usw., gestützt.
Im ersten Teil der Vorlesung sollen zwei grundlegende Paradigmen der algorithmischen Geometrie, das Sweepline-Paradigma und das Divide- und Conquer-Paradigma, anhand exemplarischer Fälle besprochen werden.
Der zweite Teil beschäftigt sich mit effizienten Algorithmen zum Berechnen von konvexen Hüllen und Voronoi-Diagrammen. Dabei werden auch konkrete Anwendungen aus dem Bereich der Computer-Graphik, des Computer Aided Design und der Robotik diskutiert. Skript (WS95/96) Übungen (alt). Übungen zur Vorlesung

Voraussetzungen:
Vordiplom (wünschenswert)

Literatur:

1. Franz Aurenhammer. Voronoi diagrams - a survey of a fundamental geometric data ACM Computing Surveys, Vol. 23:345­405, 1991.
2. H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987.
3. Steven Fortune. Voronoi diagrams and Delaunay triangulations. In D. Du and F. Hwang, editors, Computing in Euclidean Geometry, pages 193­233. World Scientific Publishers, 1992.
4. R. H. Güting. Conquering Contours: Efficient Algorithms For Computational Geometry Dissertation, Universität Dortmund, 1983
5. D.T. Lee and F.P. Preparata. Computational geometry -a survey. IEEE Transactions on Computers, Vol. C-33(12):1072­1101, 1984.
6. K. Mehlhorn Data Structures and Algorithms Springer Verlag 1994
7. F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, 1985.