VORONOI++

This project is concerned with a versatile and influential data structure called the Voronoi diagram, a geometric structure which makes explicit the proximity information exerted by a given set of sites in space. Space partitioning structures of this kind have proven useful not only in computational geometry and more applied areas of computer science, but also in the natural and economical sciences. Fast construction methods and, as a prerequisite, a thorough understanding of their structural and algorithmic properties, are in demand. In this DACH project, we intend to join forces to conduct research on some of these problems. The involved research groups (R. Klein, Bonn; E. Papadopoulou, Lugano; B. Jüttler, Linz; F. Aurenhammer, Graz) have successfully worked on this topic within the framework of EuroGIGA (initiated by F. Aurenhammer) in the Collaborative Research Project ``VORONOI``, which is documented by numerous relevant publications. Our main goal is to generalize Voronoi diagrams to such an extent that modeling real life scenarios becomes possible. The progress we have already made in previous collaborations has put this goal within our reach. Among our planned research topics are Abstract Voronoi diagrams, cluster Voronoi diagrams, anisotropic diagrams, and skeletal structures in 3D. These topics show the necessary diversity for a successful research and, on the other hand, are strongly interrelated which promises a (continuing) fruitful cooperation between the project partners. Complementing the planned theoretical research, practical aspects will be emphasized. The complexity of the structures to be investigated has reached a level where visualization tools (like interactive applets) are needed, which are intended to be made public later on. To put the findings of this project to practical use, software implementations of the developed algorithms for anisotropic Voronoi diagrams and 3D straight skeletons will be available.

So-called Voronoi diagrams are geometric data structures that models the influence a set of "sites" exert on their surrounding. The resulting partitions of the plane (or space) plays an important role in natural sciences, economics, and engineering. In this project, several types of Voronoi diagrams and related skeletal structures have been mathematically investigated, and efficient algorithms for their construction have been developed. Several respective algorithms in 2D and 3D have been implemented and tested.