Publications by year

2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  

Most documents on this website are protected by copyright. By clicking on a PDF icon, you confirm that you or your institution has the right to do so. Note that the definitive versions of all EG papers (Eurographics,...) can be downloaded from ACM papers (Siggraph, ...) can be downloaded from


“Centroidal Voronoi Tessellations for Line Segments and Graphs”
Lin Lu, Bruno Lévy and Wenping Wang
Tech report - Accepted pending revision, 2009

Abstract: TR Centroidal Voronoi Tesselation (CVT) of points has many applications in geometry processing, including re-meshing and segmentation to name but a few. In this paper, we propose a new extension of CVT, generalized to graphs. 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 approximated method to solve 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.

BibTex reference

   AUTHOR     = "Lin Lu and Bruno Lévy and Wenping Wang",
   TITLE      = "Centroidal Voronoi Tessellations for Line Segments and Graphs",
   INSTITUTION = "INRIA - ALICE Project Team",
   YEAR       = "2009",
   NOTE       = "Accepted pending revision",