Computing 2D Periodic Centroidal Voronoi Tessellation

Dong-Ming Yan 1, * Kai Wang 1, 2 Bruno Lévy 1 Laurent Alonso 1
* Auteur correspondant
1 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 GIPSA-lab - Grenoble Images Parole Signal Automatique
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.
keyword : Periodic Voronoi diagram Delaunay triangulation centroidal Voronoi tessellation hexagonal pattern
Type de document :
Communication dans un congrès
8th International Symposium on Voronoi Diagrams in Science and Engineering - ISVD2011, Jun 2011, Qingdao, China. 2011, 〈10.1109/ISVD.2011.31〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00605927
Contributeur : Dongming Yan <>
Soumis le : mardi 5 juillet 2011 - 15:47:24
Dernière modification le : lundi 9 avril 2018 - 12:22:14
Document(s) archivé(s) le : jeudi 6 octobre 2011 - 02:20:54

Fichier

pcvt2d_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | GIPSA-AGPIG | GIPSA | GIPSA-DIS | UGA | UGA-TEST-TER | LORIA | UNIV-LORRAINE

Citation

Dong-Ming Yan, Kai Wang, Bruno Lévy, Laurent Alonso. Computing 2D Periodic Centroidal Voronoi Tessellation. 8th International Symposium on Voronoi Diagrams in Science and Engineering - ISVD2011, Jun 2011, Qingdao, China. 2011, 〈10.1109/ISVD.2011.31〉. 〈inria-00605927〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

887

Téléchargements de fichiers

1876

Contact


archive-ouverte@inria.fr