Kreisexpansion und abstrakte Voronoi-Diagramme

• Antragsteller: Professor Dr. Rolf Klein
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2015 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 258414889

Voronoi-Diagramme sind Strukturen von fundamentaler Bedeutung; sie werden in der Informatik und in vielen anderen Wissenschaften verwendet. Das DACH-Projekt VORONOI++ zielt darauf ab, Voronoi-Diagramme so zu verallgemeinern, daß eine genauere Beschreibung der realen Welt möglich wird. Der deutsche Beitrag zum DACH-Projekt VORONOI++ hat folgende Ziele:1) Strukturanalyse von Voronoi-Diagrammen für verallgemeinerte Kreisausbreitung.Voronoi-Diagramme entstehen dadurch, daß sich von endlich vielen Objekten Kreise ausbreiten. Jeder Punkt gehört zur Voronoi-Region desjenigen Objekts, dessen Kreise ihn zuerst erreichen. Wir wollen erstmals untersuchen, was für Diagramme entstehen, wenn die Ausbreitungsgeschwindigkeiten nicht über die Zeit konstant sind und vom jeweiligen Objekt abhängen. Dieser Ansatz umfaßt bekannte Verallgemeinerungen des gewöhnlichen Voronoi-Diagramms durch individuelle Gewichte und fügt variable Ausbreitungsgeschwindigkeiten als neue Komponente hinzu. Erste Ergebnisse legen nahe, daß mit einem Zerfall der Voronoi-Regionen zu rechnen ist. Wir möchten herausfinden, wie die Form der Bisektoren und die strukturelle Komplexität der entstehenden Voronoi-Diagramme von den Geschwindigkeitsfunktionen abhängt.2) Verallgemeinerung abstrakter Voronoi-Diagramme und effiziente Algorithmen zu ihrer Konstruktion.Abstrakte Voronoi-Diagramme wurden 1989 vom Antragsteller als verallgemeinerndes Konzept eingeführt, um eine möglichst große Vielfalt konkreter Voronoi-Diagramme abzudecken. Sie beruhen nicht auf Orten, Kreisen oder einem Distanzbegriff, sondern auf Bisektorkurven, die gewisse einfache kombinatorische Eigenschaften aufweisen. Sind diese in einem konkreten Fall erfüllt, so sind die Strukturaussagen und effizienten Algorithmen der AVD-Theorie unmittelbar auf den konkreten Fall anwendbar; eine ganze Reihe von Autoren konnten diese Tatsache nutzen. Während bisher vorausgesetzt wurde, daß die Bisektorkurven unbeschränkt sind und zusammenhängende Regionen erzeugen, sollen diese Axiome nun gelockert werden, damit auch die unter 1) genannten Diagrammtypen, bei denen geschlossene Bisektorkurven auftreten können, und die in den anderen Teilprojekten zu untersuchenden Voronoi-Diagramme abgedeckt sind. Erste Teilergebnisse über unzusammenhängende Regionen sind ermutigend.3) Interaktive Java Applets.Um neuartige Voronoi-Diagramme zu visualisieren und Experimente zu ermöglichen, sollen interaktive Java-Applets implementiert werden. Hierbei können geometrische Primitive verwendet werden, die im Geometrylab des Antragstellers schon vorhanden sind. Die Applets werden später öffentlich zur Verfügung gestellt.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Österreich, Schweiz
• Beteiligte Institution: Schweizerischer Nationalfonds (SNF)
• Beteiligte Personen: Professor Dr. Franz Aurenhammer; Professor Dr. Bert Jüttler; Professorin Dr. Evanthia Papadopoulou