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


“Computing 2D Periodic Centroidal Voronoi Tessellation”
Dong-Ming Yan, Kai Wang, Bruno Lévy and Laurent Alonso
8th International Symposium on Voronoi Diagrams in Science and Engineering - ISVD2011

Abstract: In this paper, we propose an efficient algorithm to compute the centroidal Voronoi tessellation in 2D periodic space. We first present a simple algorithm for constructing the periodic Voronoi diagram (PVD) from a Euclidean Voronoi diagram. The presented PVD algorithm considers only a small set of periodic copies of the input sites, which is more efficient than previous approaches requiring full copies of the sites (9 in 2D and 27 in 3D). The presented PVD algorithm is applied in a fast Newton-based framework for computing the centroidal Voronoi tessellation (CVT). We observe that full-hexagonal patterns can be obtained via periodic CVT optimization attributed to the convergence of the Newton-based CVT computation.

BibTex reference

   HAL_ID     = "inria-00605927",
   URL        = "",
   TITLE      = "Computing 2D Periodic Centroidal Voronoi Tessellation",
   AUTHOR     = "Yan, Dong-Ming and Wang, Kai and Lévy, Bruno and Alonso, Laure
   BOOKTITLE  = "8th International Symposium on Voronoi Diagrams in Science and Engine
                   ering - ISVD2011",