Computing 2D periodic centroidal Voronoi tessellation

Dong Ming Yan*, Kai Wang, Bruno Levy, Laurent Alonso

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

15 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011
Pages177-184
Number of pages8
DOIs
StatePublished - 2011
Event2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011 - Qingdao, China
Duration: Jun 28 2011Jun 30 2011

Publication series

NameProceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011

Other

Other2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011
CountryChina
CityQingdao
Period06/28/1106/30/11

Keywords

  • Delaunay triangulation
  • Periodic Voronoi diagram
  • centroidal Voronoi tessellation
  • hexagonal pattern

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Computing 2D periodic centroidal Voronoi tessellation'. Together they form a unique fingerprint.

Cite this