VORONOI++

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 Konstruktions- verfahren 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.

Sogenannte Voronoi Diagramme sind geometrische Datenstrukturen, die den Einfluss von "sites" auf ihre Umgebug modellieren. Die resultierenden Aufteilungen der Ebene (oder des Raumes) spielen eine wichtige Rolle in den Naturwissenschaften, in der Oekonomie, und in den Ingenieurwissenschaften. In diesem Projekt wurden mehrere Typen von Voronoi Diagrammen und verwandte skeletale Strukturen mathematisch untersucht, und effiziente Algorithmen fuer ihre Konstruktion wurden entwickelt. Mehrere dieser Algorithmen in 2D und 3D wurden implementiert und getestet.