Algorithmische Geometrie (251-0419-00) WS05/06

Upon request, this course will be held in English.

Termine

Vorlesung: Montag 13:15-15:00, CAB G59

Bernd Gärtner,	CAB G32.2,	Tel: 01-632 70 26,		.
Michael Hoffmann,	CAB G33.1,	Tel: 01-632 73 90,		.

Übung: Montag 15:00-16:00, CAB G59

Eva Schuberth,

CAB G17,

Tel: 01-632 69 86.

Hinweis: Am Montag, den 14. November ist der Tag der Lehre. Deshalb finden Vorlesung und Übung nicht statt.

Inhalt

In der algorithmischen Geometrie geht es um den Entwurf und die Analyse effizienter Algorithmen für geometrische Probleme. Diese werden in vielen Anwendungen benötigt, z.B. bei der Kurven- und Oberflächenrekonstruktion aus Scanner-Daten, der Visualisierung grosser Datenmengen, oder Ähnlichkeitsabfragen in Datenbanken.

In der Vorlesung werden einige der grundlegenden geometrischen Datenstrukturen behandelt und wichtige Entwurfsparadigmen für geometrische Algorithmen vorgestellt. Die konkrete Anwendbarkeit sowie praktische Aspekte des erlernten Materials werden in den Übungen mit Hilfe der CGAL-Bibliothek diskutiert; CGAL stellt eine grosse Anzahl geometrischer Datenstrukturen und Algorithmen in einer flexiblen Form in C++ zur Verfügung.

Die Vorlesung wird im darauffolgenden Semester mit einem Seminar ergänzt; ferner besteht die Möglichkeit, im Anschluss an Vorlesung oder Seminar eine Semester-, Diplom- oder Masterarbeit im Gebiet der Algorithmischen Geometrie zu schreiben.

Hinweise zur Übung

Die Übungsblätter werden in der Vorlesung ausgegeben. Die Übungsaufgaben sind schriftlich zu bearbeiten und zu Beginn der darauffolgenden Vorlesungsstunde abzugeben. Gruppenabgabe und das Einreichen identischer Lösungen sind nicht zulässig.

Unter den Aufgaben werden auch einige Programmieraufgaben (in C++) sein, jedoch keine aufwändigen Projekte, sondern eher kleinere Anpassungen an vorgegebenen Programmgerüsten.

Die abgegebenen Übungsaufgaben werden benotet. Werden mindestens 80 % der möglichen Punkte erreicht, so entspricht das der Note 6.0.

Prüfung

Die Prüfung ist mündlich und dauert 15 Minuten. Die Gesamtnote setzt sich zu 50 % aus der Note für die Übungsaufgaben und zu 50 % aus der erbrachten Prüfungsleistung zusammen.

Literatur

• Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer, 2000.
• Franco P. Preparata, Michael I. Shamos, Computational Geometry: An Introduction, Springer, 1985.
• Bernd's Skript aus Berlin von 1996