FWF - EuroGIGA - Erweiterte Voronoi (Delaunay) Strukturen

In diesem Teilprojekt sollen anspruchvolle und zugleich vielverprechende offene theoretische Fragen zu erweiterten Voronoi und Delaunay Strukturen untersucht werden. Diese Fragen haben vielfältige Anwendungen, sowie eine lange Geschichte, in die der Antragsteller involviert ist. Mehrere andere Teilprojekte (IPs) innerhalb des gegenständlichen Verbundprojekts (CRP) haben einschlägige Vorarbeiten geleistet, die nun fortgeführt, koordiniert und intensiviert werden sollen. Wir sind überzeugt, dass ein europaweites Forschungsnetzwerk, das im Gesamt- EuroGIGA Unternehmen wohleingebettet ist, die richtige und zeitgerechte Gelegenheit bietet, diese Probleme erfolgreich zu behandeln. Vier Problemkreise sollen untersucht werden. Der erste behandelt sogenannte shape-Delaunay Strukturen. Dies sind nützliche Verallgemeinerungen der vielverwendeten Delaunay Triangulierung in der Computerwissenschaft. Etliche interessante Fragen erheben sich, wenn die "leere Kreis Eigenschaft" durch allgemeinere Formen ersetzt wird. Der zweite Problemkreis ist verwandt: kurze Delaunay Flip Sequenzen mittels Pseudo-Triangulierungen. Straight Skeletons und ihre strukturellen und algorithmischen Eigenschaften, die immer noch nicht befriedigend erforscht sind, stellen den dritten zu untersuchenden Problemkreis dar. Schließlich soll eine neue und herausfordernde Variante von Voronoi Diagrammen, die sog. Zonen-Diagramme, erforscht werden. Shape Delaunay Strukturen haben Anwendungen z.B. bei der Konstruktion von effizienten Spann-Graphen (untersucht in IP3), und sind nahe verwandt mit geometrischen Nachbarschaftsgraphen (Gegenstand von IP6). Die Forschungsgruppe um IP5 hat Vorarbeiten zu Shape Delaunay Strukturen geleistet, ein weiterer Punkt für Kollaboration. Pseudo-Triangulierungen wurden in der Gruppe um G. Rote (IP4) erforscht. Für neue Zugänge zur Konstruktion von Straight Skeletons wird die Expertise in IP5 betreffend Polygone und skeletale Strukturen hilfreich sein. Weiters ist zu erwarten, dass sich Methoden in IP2 für die Konstruktion von Mittelachsen anwenden lassen. Bei achsenparallelen Polygonen (IP7) ist die Situation besser verstanden. Zonen-Diagramme und ihre Varianten werden gemeinsam mit IP4 erforscht.