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.

Zerlegungsstrukturen für geometrische Objekte sind ein wichtiges Mittel zur Strukturierung und Verarbeitung von Computerdaten verschiedener Art. Sie finden Anwendungen im Computer Aided Design, Numeric Control, Graphics&Vision, Medical Computing, Geographischen Informationssystemen und anderen Bereichen. Das gegenständliche Projekt leistet einen Beitrag zum Stand der Forschung über geometrische Zerlegungsstrukturen. Viele Anwendungen verlangen nach einem Dreiecksnetz, welches das zu verarbeitende Objekt beschreibt. Im Projekt wurden mehrere strukturelle und algorithmische Fragen zu solchen Triangulierungen untersucht, unter anderem die Erzeugung von richtungs- abhängigen Netzen, und Netzen mit Kreisbögen als Kanten (die darüber hinaus im Graph Drawing Verwendung finden).Eine der populärsten Zerlegungsstrukturen, auch in den Naturwissenschaften, ist das Voronoi Diagramm. Während der Laufzeit des Projektes wurde das weltweit erste Buch über Voronoi Diagramme geschrieben, das die Thematik aus Sicht eines Computerwissenschaftlers beschreibt. Weiters wurden neue Ergebnisse zu gewissen verallgemeinerten Voronoi Diagrammen erhalten. Solche Diagramme treten in verschiedenen Problemen auf, wo Abstände unter anisotropen Bedingungen, oder unter Sichtbarkeitseinschränkungen, gemessen werden müssen. Mit Hilfe von skeletalen Strukturen versucht man, die wichtigen Informationen für ein geometrisches Objekt zu bündeln. Die weitverbreitetste solche Struktur ist die Mittelachse, die jedoch den Nachteil aufweist (vor allem in 3D), gekrümmte Elemente zu enthalten. Eine Alternative - schon seit einiger Zeit erfolgreich in 2D eingesetzt -- ist das Straight Skeleton. Diese Struktur entsteht durch einen Offsetting Prozess des Input-Objekts. Wir entwickeln erstmals eine präzise Definition des Offsetting Prozesses in 3D für polygonale Netze, und damit für Straight Skeletons in 3D. Dies ermöglicht stückweise-lineare Lösungen für verschiedene Probleme, etwa in CAD und MC, wo bisher Heuristiken verwendet werden mussten. Die meisten der entwickelten Algorithmen wurden auch implementiert. Dies einerseits dazu, um Einsichten über diese teils sehr komplexen geometrischen Zerlegungsstrukturen zu gewinnen, aber auch, um ihre Verwendbarkeit in der Praxis anzutesten.