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


“Efficient Computation of 3D Clipped Voronoi Diagram”
Dong-Ming Yan, Wenping Wang, Bruno Lévy and Yang Liu
GMP 2010 Conference Proceedings

Abstract: The Voronoi diagram is a fundamental geometry structure widely used in various fields, especially in computer graphics and geom- etry computing. For a set of points in a compact 3D domain (i.e. a finite 3D volume), some Voronoi cells of their Voronoi diagram are infinite, but in practice only the parts of the cells inside the domain are needed, as when computing the centroidal Voronoi tessellation. Such a Voronoi dia- gram confined to a compact domain is called a clipped Voronoi diagram. We present an efficient algorithm for computing the clipped Voronoi di- agram for a set of sites with respect to a compact 3D volume, assuming that the volume is represented as a tetrahedral mesh. We also describe an application of the proposed method to implementing a fast method for optimal tetrahedral mesh generation based on the centroidal Voronoi tessellation.

BibTex reference

   AUTHOR     = "Dong-Ming Yan and Wenping Wang and Bruno Lévy and Yang Liu",
   TITLE      = "Efficient Computation of 3D Clipped Voronoi Diagram",
   BOOKTITLE  = "GMP 2010 Conference Proceedings",