Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion
No Thumbnail Available
Date
2017
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and John Wiley & Sons Ltd.
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.
Description
@article{10.1111:cgf.13116,
journal = {Computer Graphics Forum},
title = {{Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion}},
author = {Herholz, Philipp and Haase, Felix and Alexa, Marc},
year = {2017},
publisher = {The Eurographics Association and John Wiley & Sons Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/cgf.13116}
}