| |
| Arbeitsbereich: | Bioinformatik |
| Dozent: | Dr. Olaf Delgado-Friedrichs |
| Sprechstunde: | Sand 14 Raum C309, Mo 16-18 |
| Zeit: | Mi 13-15, Übungen
Mi 12-13 und Mi 15-16 |
|
| Umfang: | 2(+1) |
| Ort: | Sand 6/7, kleiner
Hörsaal (Raum 122) | |
| Turnus: | traditionell 2-semestrig, zur Zeit 2-jährig |
| Pruefungsfach: | Theoretische und Praktische Informatik |
| Vorlesungsskript: |
Kapitel 1-3
(Stand: 04.12.2002) |
|
Kapitel 4-6
(Stand: 29.01.2003, Neu ab Seite 75) |
| Beschreibung: |
| In der algorithmischen Geometrie geht es um die Entwicklung effizienter Algorithmen für Probleme der diskreten und kombinatorischen Geometrie. Die betrachteten Objekte sind elementar - Punkte, Geraden, Strecken und so weiter. Komplexität entsteht erst aus dem Zusammenspiel vieler einfacher Elemente.
Der Schnittpunkt zweier Geraden zum Beispiel läßt sich leicht ausrechnen. Möchte man dagegen verstehen, wie ein Arrangement von hunderten oder gar tausenden von Geraden die Ebene zerteilt, so werden plötzlich geschickte Algorithmen und geeignete Datenstrukturen interessant.
Die Vorlesung diskutiert klassische Probleme wie Polygonzerlegung, konvexe Hüllen, Voronoi-Diagramme, Arrangements, Such- und Schnittprobleme und deren Anwendungen. Einige grundlegende Algorithmen und Paradigmen werden exemplarisch vorgestellt.
|
| Voraussetzung: |
| Grundstudium (insbesondere Algorithmen und Datenstrukturen). |
| Literatur: |
-
Franz Aurenhammer. Voronoi diagrams - a survey of a fundamental geometric data structure. ACM Computing Surveys, Vol. 23:345-405, 1991.
-
Mark de Berg et al. Computational Geometry - Algorithms and
Applications (2nd edition). Springer-Verlag, 2000.
-
H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, 1987.
-
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.
-
R. Klein. Algorithmische Geometrie. Addison-Wesley-Longman-Verlag, 1997.
-
D.T. Lee and F.P. Preparata. Computational geometry -a survey. IEEE Transactions on Computers, Vol. C-33(12):1072-1101, 1984.
-
K. Mehlhorn Data Structures and Algorithms. Springer-Verlag, 1994.
-
F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, 1985.
-
J. O'Rourke. Computational Geometry In C. Cambridge University Press, 1993.
|
|
Teaching