Dozent | Dr. R. Klein, Dr. K. Reinhardt |
Sprechstunde | R. Klein: Mi. 10-11; Morgenstelle C9 P10, Tel 29-75462, K. Reinhard: Sand 13, Raum 004, Tel 29-78964 |
Zeit | Do 1416 |
Umfang | 2+2 |
Beginn | 16.10.97 |
Ort | Morgenstelle, C9 G06 |
Turnus | möglicherweise 2-semestrig |
Prüfungsfach | Theoretische und Praktische Informatik |
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: