Zentrales Thema dieser gemeinsamen Forschung ist die Untersuchung
grundlegender Datenstrukturen aus dem Bereich der rechnerischen
Geometrie (Computational Geometry), einem relativ jungen Teilgebiet
der (theoretischen) Informatik. Dabei sollen sowohl theoretische
Aspekte untersucht werden, als auch deren konkrete Umsetzung im Rahmen
einer allgemein verwendbaren Programmbibliothek.
Auf Seite der theoretischen Untersuchungen sollen sowohl klassische
Datenstrukturen, wie Voronoi-Diagramme oder Triangulierungen, aber auch
relativ neue Datenstrukturen, wie Pseudo-Triangulierungen oder
Straight-Skeletons, untersucht werden. Genauere Einzelheiten werden in
den nachfolgenden Abschnitten beschrieben. Gleichzeitig soll aber auch
für alle untersuchten Strukturen deren tatsächliche
Verwendbarkeit in der Praxis berücksichtigt werden. So ist es
geplant, jeweils spezielle Aspekte dieser Strukturen in konkreten
Implementationen umzusetzen. Um einen bestmöglichen Nutzen der
erzielten Ergebnisse zu gewährleisten, sollen die Implementationen
in einer standardisierten Bibliothek der gesamten CG-Community zur
Verfügung gestellt werden. Dazu ist die Umsetzung in CGAL
(Computational Geometry Algorithms Library, siehe { www.cgal.org})
geplant. Es handelt sich dabei um ein ursprünglich von
der EU gefördertes Projekt, das insbesondere von unserem
französichen Projektpartner an zentraler Stelle mitbetrieben wird.