392162 Computational Geometry (S) (SoSe 2005)

Wir wollen in diesem Literaturseminar eine Einführung in das Gebiet der Algorithmische Geometrie (Computational Geometry) geben. Die Algorithmische Geometrie entstand in den späten 70er Jahren aus Teilgebieten der Algorithmik und der Komplexitätstheorie. Das Forschungsgebiet bezieht seinen Reiz zum einen daraus, dass sich die behandelten Probleme natürlich aus ihrer geometrischen Interpretation ergeben: Beispielsweise, zu einer Punktmenge das kleinste umschließende Polygon zu finden. Zum anderen spielen solche Probleme eine wichtige Rolle in Anwendungen wie der Robotik, der Computergrafik, und sogar der Bioinformatik.

Im Seminar werden wir anhand des Buches "Computational Geometry" (de Berg et al) die Ideen und Algorithmen nachvollziehen, die in der Algorithmischen Geometrie entwickelt wurden.

Bibliography

M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry. 2. Auflage, Springer-Verlag, 2000. ISBN: 3-540-65620-0. Preis ca. 35 Euro.