Funding & Project no.: FWF, I1836-N15
Project leader: Franz Aurenhammer
Duration: 01.Juni 2015 - 31. Mai 2020
Abstract: 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.
Partner: Johannes Kepler Universität Linz (JKU)
