Circle Expansion and abstract Voronoi diagrams

• Applicant: Professor Dr. Rolf Klein
• Subject Area: Theoretical Computer Science
• Term: from 2015 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 258414889

Voronoi diagrams are structures of fundamental importance; they have applications in computer science and in many other sciences. The DACH project VORONOI++ is aiming to generalize the concept of Voronoi diagrams to an extent that more precise models of the real world become possible. The german part of the DACH project VORONOI++ has the following goals.1) Analysis of Voronoi diagrams based on generalized circle expansion.Voronoi diagrams result from circles expanding from a finite set of sites. Each point belongs to the Voronoi region of that site whose circles reach it first. For the first time, we want to investigate what diagrams result if the expansion speeds are not constant over time, and depend on the sites. This approach includes known generalizations of standard Voronoi diagrams by individual weights, and adds variable speeds as a new component. First results indicate that Voronoi regions are likely to become disconnected. We would like to find out how the bisector shapes and the structural complexity of the resulting Voronoi diagrams depend on the individual speed functions. 2) Generalization of abstract Voronoi diagrams and efficient algorithms for constructing them.Abstract Voronoi diagrams (AVDs) were introduced by the applicant in 1989 as a unifying concept, to cover as many as possible concrete types of Voronoi diagrams. They are not based on sites, circles, or distance measures, but on bisecting curves that have certain simple combinatorial properties. Whenever these are fulfilled in a concrete situation, structure results and efficient algorithms from AVD theory can be directly applied to the concrete case; quite a few authors were able to make use of this fact. So far bisectors were supposed to be unbounded, and to generate connected Voronoi regions. These axioms shall now be relaxed in order to cover the diagrams mentioned in 1), which may exhibit closed bisector curves, as well as the diagram types studied in the other VORONOI++ projects. First results on disconnected regions are encouraging.3) Interactive Java applets.In order to study new types of Voronoi diagrams, and to perform experiments, interactive Java applets shall be implemented. Here we can build on geometric primitives available in the applicant's geometry lab. Later, these applets will be made available to the community.

• DFG Programme: Research Grants
• International Connection: Austria, Switzerland
• Participating Institution: Schweizerischer Nationalfonds (SNF)
• Participating Persons: Professor Dr. Franz Aurenhammer; Professor Dr. Bert Jüttler; Professorin Dr. Evanthia Papadopoulou