Implementierung Geometrischer Algorithmen

Gegenstand der Algorithmischen Geometrie ist die Entwicklung von effizienten Algorithmen zur Lösung geometrischer Probleme und die der Bestimmung der algorithmischen Komplexität geometrischer Probleme. Geometrische Probleme treten in einer Vielzahl von Anwendungsgebieten auf, z.B. in der Computergrafik, der Robotik, der Kartographie, beim VLSI-Entwurf, beim Bildverstehen, beim computerunterstützten Entwurf (CAD) oder bei der Modellierung von Molekülen. Geometry in Action gibt eine schöne Übersicht mit vielen Beispielen. Unter anderem finden Sie als Beispiel für die Anwendung von Voronoidiagrammen folgende Abbildung:

Die Sternchen markieren Niederlassungen einer Fast-Food-Kette in einem Teilgebiet San Franciscos. Das von der äußeren roten Linie begrenzte Teilgebiet ist so in Regionen weiter unterteilt, daß die in einer Region liegende Niederlassung für alle Orte in dieser Region von allen Niederlassungen die nächstgelegene ist.
Im FoPra werden effiziente Algorithmen, die im Bereich Algorithmische Geometrie entwickelt wurden, mithilfe von

und

in C++ implementiert.

Last changed on 03 Aug 98