Centroidal Voronoi Tessellation of Line Segments and Graphs

Simple item page
dc.contributor.authorLu, Linen_US
dc.contributor.authorLévy, Brunoen_US
dc.contributor.authorWang, Wenpingen_US
dc.contributor.editorP. Cignoni and T. Ertlen_US
dc.date.accessioned2015-02-28T06:57:25Z
dc.date.available2015-02-28T06:57:25Z
dc.date.issued2012en_US
dc.description.abstractCentroidal Voronoi Tessellation (CVT) of points has many applications in geometry processing, including remeshing and segmentation, to name but a few. In this paper, we generalize the CVT concept to graphs via a variational characterization. Given a graph and a 3D polygonal surface, our method optimizes the placement of the vertices of the graph in such a way that the graph segments best approximate the shape of the surface. We formulate the computation of CVT for graphs as a continuous variational problem, and present a simple, approximate method for solving this problem. Our method is robust in the sense that it is independent of degeneracies in the input mesh, such as skinny triangles, T-junctions, small gaps or multiple connected components. We present some applications, to skeleton fitting and to shape segmentation.en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume31
dc.identifier.doi10.1111/j.1467-8659.2012.03058.x
dc.identifier.issn1467-8659en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2012.03058.xen_US
dc.publisherThe Eurographics Association and John Wiley and Sons Ltd.en_US
dc.titleCentroidal Voronoi Tessellation of Line Segments and Graphsen_US
Files
Collections
31-Issue 2
Full Papers 2012 - CGF 31-Issue 2