Lu, LinLévy, BrunoWang, WenpingP. Cignoni and T. Ertl2015-02-282015-02-2820121467-8659https://doi.org/10.1111/j.1467-8659.2012.03058.xCentroidal 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.10.1111/j.1467-8659.2012.03058.x