Voronoi diagrams are fundamental geometric structures that divide space into regions based on proximity to points or sites. They play an important role in many fields of science and have become cornerstones of disciplines such as computational geometry, scientific computing, and optimization.

At the heart of this Dagstuhl Seminar are generalized Voronoi diagrams, with a primary focus on Laguerre diagrams and their rather recent generalizations – anisotropic power diagrams and generalized balanced power diagrams – which introduce piecewise quadratic cell boundaries, enabling more precise modeling of complex structures.

Recently these diagrams have drawn significant interest from the materials science community for their remarkable ability to accurately depict the inner structures of polycrystalline materials, such as metals, ceramics, and rocks, offering valuable insights into their composition and properties. Due to their ability to follow more complex boundary structures, they are also of emerging interest in Voronoi-based image processing applications, e.g., in superpixel generation and image segmentation.

Current methods for computing generalized Voronoi diagrams from imaging data are limited to moderately sized diagrams comprising of about 1,000-10,000 regions. To handle large data sets enabling computations at high resolution, large sample size, and multiple time steps, it is vital to develop efficient algorithms. However, the research communities behind the algorithm development, geometric clustering, optimal transport, stochastic geometry, and computational geometry are largely disjoint, with each field relying on different mathematical foundations and techniques.

The goal of this Dagstuhl Seminar is to bring together leading researchers from these areas and imaging applications to learn from each other, spark vibrant discussions, identify common grounds, advance their fields, and set the path for successful collaborations towards developing fast and robust generalized Voronoi diagram algorithms addressing the needs of the practitioners working in imaging and microstructure modelling.

Creative Commons BY 4.0

Andreas Alpers, David Bourne, Henning Poulsen, and Claudia Redenbach