Computing 2D periodic centroidal Voronoi tessellation

Dong Ming Yan; Kai Wang; Bruno Levy; Laurent Alonso

doi:10.1109/ISVD.2011.31

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 proceeding › Conference contribution › peer-review

20 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 language	English (US)
Title of host publication	Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011
Pages	177-184
Number of pages	8
DOIs	https://doi.org/10.1109/ISVD.2011.31
State	Published - 2011
Externally published	Yes
Event	2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011 - Qingdao, China Duration: Jun 28 2011 → Jun 30 2011

Publication series

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

Other

Other	2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011
Country/Territory	China
City	Qingdao
Period	06/28/11 → 06/30/11

Keywords

Delaunay triangulation
Periodic Voronoi diagram
centroidal Voronoi tessellation
hexagonal pattern

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1109/ISVD.2011.31

Cite this

Yan, D. M., Wang, K., Levy, B., & Alonso, L. (2011). Computing 2D periodic centroidal Voronoi tessellation. In Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011 (pp. 177-184). Article 5988933 (Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011). https://doi.org/10.1109/ISVD.2011.31

@inproceedings{eec7d449882d4f57aa5a16ac2ba1ff92,

title = "Computing 2D periodic centroidal Voronoi tessellation",

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.",

keywords = "Delaunay triangulation, Periodic Voronoi diagram, centroidal Voronoi tessellation, hexagonal pattern",

author = "Yan, {Dong Ming} and Kai Wang and Bruno Levy and Laurent Alonso",

note = "Copyright: Copyright 2011 Elsevier B.V., All rights reserved.; 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011 ; Conference date: 28-06-2011 Through 30-06-2011",

year = "2011",

doi = "10.1109/ISVD.2011.31",

language = "English (US)",

isbn = "9780769544830",

series = "Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011",

pages = "177--184",

booktitle = "Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011",

}

Yan, DM, Wang, K, Levy, B & Alonso, L 2011, Computing 2D periodic centroidal Voronoi tessellation. in Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011., 5988933, Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011, pp. 177-184, 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011, Qingdao, China, 06/28/11. https://doi.org/10.1109/ISVD.2011.31

Computing 2D periodic centroidal Voronoi tessellation. / Yan, Dong Ming; Wang, Kai; Levy, Bruno et al.
Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011. 2011. p. 177-184 5988933 (Proceedings - 2011 8th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Computing 2D periodic centroidal Voronoi tessellation

AU - Yan, Dong Ming

AU - Wang, Kai

AU - Levy, Bruno

AU - Alonso, Laurent

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Delaunay triangulation

KW - Periodic Voronoi diagram

KW - centroidal Voronoi tessellation

KW - hexagonal pattern

UR - http://www.scopus.com/inward/record.url?scp=80052621983&partnerID=8YFLogxK

U2 - 10.1109/ISVD.2011.31

DO - 10.1109/ISVD.2011.31

M3 - Conference contribution

AN - SCOPUS:80052621983

SN - 9780769544830

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

SP - 177

EP - 184

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

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

Y2 - 28 June 2011 through 30 June 2011

ER -

Computing 2D periodic centroidal Voronoi tessellation

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this