Diffusion Diagrams:
Voronoi Cells and Centroids from Diffusion

Philipp Herholz Felix Haase Marc Alexa

Technische Universität Berlin

Abstract We define Voronoi cells and centroids based on heat diffusion. These heat cells and heat centroids coincide with the common definitions in Euclidean spaces. On curved surfaces they compare favorably with definitions based on geodesics: they are smooth and can be computed in a stable way with a single linear solve. We analyze the numerics of this approach and can show that diffusion diagrams converge quadratically against the smooth case under mesh refinement, which is better than other common discretization of distance measures in curved spaces. By factorizing the system matrix in a preprocess, computing Voronoi diagrams or centroids amounts to just back-substitution. We show how to localize this operation so that the complexity is linear in the size of the cells and not the underlying mesh. We provide several example applications that show how to benefit from this approach.

Preprint (17MB)




Results Centroidal Voronoi diagrams can be efficiently computed using our algorithm. Some results are shown below.

@Article{Herholz:2015:DD, journal = {Computer Graphics Forum (Proc. of Eurographics)}, title = {{Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion}}, author = {Philipp Herholz and Felix Haase and Marc Alexa}, pages = {}, volume= {}, number= {}, year = {2017}, DOI = {}, }