Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion. (23rd May 2017)

• Record Type: Journal Article
• Authors: Herholz, Philipp; Haase, Felix; Alexa, Marc
• Is Part Of: Computer graphics forum. Volume 36:Number 2(2017)
• Page Start: 163
• Page End: 175
• Publication Date: 2017-05-23
• Subjects: Categories and Subject Descriptors (according to ACM CCS) -- I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Geometric algorithms; Computer graphics -- Periodicals; 006.605
• DOI: 10.1111/cgf.13116
• Languages: English
• ISSNs: 0167-7055

Abstract

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.