EuroGIGA_Advanced Voronoi (Delaunay) Structures

The aim of this individual project is to address challenging though promising open theoretical questions concerning advanced Voronoi and De- launay structures. These problems have various applications, and a quite long history with the PI strongly involved. Several other individual projects in the present CRP have done previous relevant work, and we are planning to continue, coordinate, and intensify these efforts. We are convinced this is the right opportunity and point in time to attack these problems in a European-wide research network on this topic, which is well embedded in the overall EuroGIGA project. Four topics are to be addressed within this individual project. The first one deals with so-called shape-Delaunay structures. These are useful gen- eralizations of the ubiquitous Delaunay triangulation in computer science. Several interesting questions arise when the "empty circle property" is re- placed by an "empty shape property". The second topic is related, namely, short Delaunay flip sequences via pseudo-triangulations. Straight skeletons and their structural and algorithmic properties, which are still not under- stood at a satisfactory level, are topic three. Finally, a new and challenging type of Voronoi diagram, the so-called zone diagram, will be investigated. Shape Delaunay structures have applications, for example, in finding effi- cient spanner graphs, which will be investigated in IP3, and they are strongly related to geometric neighborhood graphs which are the topic of IP6. The group around IP5 has done previous work on shape Delaunay structures, which constitutes another planned collaboration. Pseudo- triangulations have also been investigated in the group of G. Rote (IP4). For finding novel ap- proaches to the straight skeleton construction, the expertise of the group in IP5 on polygons and skeletons will be sought. Also, the methods investi- gated in IP2 for medial axis constructions are likely carry over to straight skeletons. For rectilinar polygons (IP7), the situation is better understood. Zone diagrams and their variants will be investigated jointly with IP4.

Partitioning structures for geometric objects are an important means in computer science for structuring and processing data of various kinds. They have applications in Computer Aided Design, Numeric Control, Graphics and Vision, Medical Computing, Geographical Information Systems, and others. This project contributes to the state-of-the-art of geometric partitioning structures. Many applications ask for generating a triangular mesh describing the object to be processed. We have studied several structural and algorithmic questions on such triangulations, including the generation of direction-sentitive meshes, and meshes with curved edges (which are additionally useful in graph drawing). One of the most popular space partitioning structures, also in the natural sciences, is the Voronoi diagram. We have written a world-wide first book on that topic, from the point of view of a computer scientist. Also, new results on certain types of generalized Voronoi diagrams have been obtained, which arise in problems where distances have to be measured under anisotropic conditions or visibility constraints. Skeletal structures try to capture the basic information about a geometric input object in a simple and computationally useful way. A widely used skeleton is the medial axis, but this concept suffers from the fact that curved elements arise, especially in 3D. An alternative, which has been used successfully for some time already in 2D, is the straight skeleton, a structure coming from offsetting the input object. We develop the first precise definition for mitered offsets of polygonal surfaces in 3D, and with it, for the straight skeleton in 3D. This enables piecewise-linear solutions for several problems, for example in CAD and NC, where offsetting heuristics have been used so far. Most of the developed algorithm also have been implemented. On the one hand, this helped us to gain more insight into these sometimes very complicated geometric partitioning structures, and on the other, this gave an impression about the usability of the new structures in practice.