Diffusion Diagrams: Voronoi Cells and Centroids from Diffusion

Simple item page
dc.contributor.authorHerholz, Philippen_US
dc.contributor.authorHaase, Felixen_US
dc.contributor.authorAlexa, Marcen_US
dc.contributor.editorLoic Barthe and Bedrich Benesen_US
dc.date.accessioned2017-04-22T16:26:01Z
dc.date.available2017-04-22T16:26:01Z
dc.date.issued2017
dc.description.abstractWe 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.en_US
dc.description.number2
dc.description.sectionheadersGeometry Processing
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume36
dc.identifier.doi10.1111/cgf.13116
dc.identifier.issn1467-8659
dc.identifier.pages163-175
dc.identifier.urihttps://doi.org/10.1111/cgf.13116
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13116
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectI.3.5 [Computer Graphics]
dc.subjectComputational Geometry and Object Modeling
dc.subjectGeometric algorithms
dc.titleDiffusion Diagrams: Voronoi Cells and Centroids from Diffusionen_US
Files
Collections
36-Issue 2