inria-00605927, version 1
Computing 2D Periodic Centroidal Voronoi Tessellation
Dong-Ming Yan
a, 1Kai Wang b, 1, 2Bruno Lévy
1Laurent Alonso a, 1
8th International Symposium on Voronoi Diagrams in Science and Engineering - ISVD2011 (2011)
Résumé : 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.
- a – INRIA
- b – CNRS
- 1 : ALICE (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- 2 : Grenoble Images Parole Signal Automatique (GIPSA-lab)
- CNRS : UMR5216 – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – Université Stendhal - Grenoble III – Institut Polytechnique de Grenoble - Grenoble Institute of Technology
- Domaine : Informatique/Synthèse d'image et réalité virtuelle
- Mots-clés : Periodic Voronoi diagram – Delaunay triangulation – centroidal Voronoi tessellation – hexagonal pattern
- inria-00605927, version 1
- http://hal.inria.fr/inria-00605927
- oai:hal.inria.fr:inria-00605927
- Contributeur : Dongming Yan
- Soumis le : Mardi 5 Juillet 2011, 15:47:24
- Dernière modification le : Mardi 5 Juillet 2011, 16:04:32
Documents associés
Exporter