FWF - VORONOI++ - Kreisexpansion und abstrakte Voronoi-diagramme

Das vorliegende Forschungsprojekt hat eine vielseitige und bedeutende Datenstruktur zum Inhalt, das sogenannte Voronoi Diagramm -- eine geometrische Struktur, die den Einfluss von vorgegebenen Sites auf ihre Umgebung verdeutlicht. Partitionsstrukturen dieser Art haben sich nicht nur in der Computational Geometry und in angewandteren Bereichen der Computerwissenschaften als nützlich erwiesen, sondern auch in der Natur- und Wirtschaftswissenschaft. Dementsprechend sind schnelle Konstruktionsverfahren gefordert, und als Voraussetzung ein grundlegendes Verständnis ihrer strukturellen und algorithmischen Eigenschaften. Dieses DACH Projekt soll vorhandenes Forschungspotential vereinen, um an einigen relevanten Themen zu arbeiten. Die involvierten Forschungsgruppen (R. Klein, Bonn; E. Papadopoulou, Lugano; B. Jüttler, Linz; F. Aurenhammer, Graz) haben im Rahmen des Collaborative Research Projekts VORONOI'' bereits erfolgreich einschlägig kooperiert (siehe entsprechende Publikationslisten). Unser Hauptziel ist es, Voronoi Diagramme soweit zu verallgemeinern, dass reale Szenarien zufriedenstellend modelliert werden können. Der bisherige Erfolg bringt dieses Ziel nun in Reichweite. Geplante Forschungsthemen sind Abstrakte Voronoi Diagramme, Cluster Voronoi Diagramme, anisotropische Diagramme und skeletale Strukturen in 3D. Diese Themen enthalten die notwendige Vielfalt für erfolgreiche Forschung, sind aber andererseits stark verwandt und garantieren eine fruchtbringende Zusammenarbeit der Projektpartner. In Ergänzung zur geplanten theoretischen Forschung sollen praktische Aspekte betont werden. Die Komplexität der zu untersuchenden Strukturen erfordert Visualisierungs- Tools zum besseren Verständnis ihrer Zusammenhänge (z.B. interaktive Applets, später öffentlich zugänglich). Weiters sollen Software-Implementierungen der entwickelten Algorithmen für anisotropische Voronoi Diagramme und 3D Straight Skeletons verfügbar werden.