Algorithmische Geometrie


Dozent PD. Dr. K. Reinhardt Sprechstunde Sand 13, Raum 12
ZeitMo 12:15-15:00 Umfang3
Beginn13.10.04 OrtRaum C118, Sand 14,
Turnus2-jährig Prüfungsfach Theoretische und Praktische Informatik
Übungen im Anschluss an die Vorlesung

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: Teil1, Teil2, Teil3, Teil4, Teil5.

Übungsaufgaben: hier

Literatur: Signatur in WSI-Bib

  1. de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf. Computational geometry : algorithms and applications, 2000 F.2.2
  2. Franz Aurenhammer. Voronoi diagrams - a survey of a fundamental geometric data ACM Computing Surveys, Vol. 23:345­405, 1991.
  3. H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987. I.3.5
  4. 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.
  5. Goodman, Jacob E.O'Rourke, Joseph. Handbook of discrete and computational geometry, 1997 G.2
  6. R. H. Güting. Conquering Contours: Efficient Algorithms For Computational Geometry Dissertation, Universität Dortmund, 1983
  7. Rolf Klein. Algorithmische Geometrie. Addison-Wesley-Longman-Verlag, 1997. I.3.5
  8. D.T. Lee and F.P. Preparata. Computational geometry -a survey. IEEE Transactions on Computers, Vol. C-33(12):1072­1101, 1984.
  9. K. Mehlhorn Data Structures and Algorithms Springer Verlag 1994. F.2.2
  10. F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, 1985. I.3.5