Algorithmische Geometrie


Dozent Dr. K. Reinhardt Sprechstunde Sand 13, Raum 12
ZeitMi 15:15-16:45 Umfang2(+1)
Beginn20.10.04 OrtRaum 12, Sand 13,
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.

Wer an den Übungen teilnehmen möchte und noch keinen WSI-account hat, möge das Formular ausfüllen.

Übungsaufgaben: hier

Anmeldung zu den Übungen

Matrnr.: Nachname: Vorname:
Gruppe: Studienfach: Fachsemester:
Geburtsdatum (wird für den Schein benötigt) : email:

Literatur: Signatur in WSI-Bib

  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. I.3.5
  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. Rolf Klein. Algorithmische Geometrie. Addison-Wesley-Longman-Verlag, 1997. I.3.5
  6. D.T. Lee and F.P. Preparata. Computational geometry -a survey. IEEE Transactions on Computers, Vol. C-33(12):1072­1101, 1984.
  7. K. Mehlhorn Data Structures and Algorithms Springer Verlag 1994. F.2.2
  8. F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, 1985. I.3.5