zbMATH — the first resource for mathematics

The optimal centroidal Voronoi tessellations and the Gersho’s conjecture in the three-dimensional space. (English) Zbl 1077.65019
Summary: Optimal centroidal Voronoi tessellations have important applications in many different areas such as vector quantization, data and image processing, clustering analysis, and resource management. In the three-dimensional Euclidean space, they are also useful to the mesh generation and optimization.
We conduct extensive numerical simulations to investigate the asymptotic structures of optimal centroidal Voronoi tessellations for a given domain. Such a problem is intimately related to the famous of A. Gersho’s conjecture [IEEE Trans. Inf. Theory 25, 373–380 (1979; Zbl 0409.94013)], for which a full proof is still not available. We provide abundant evidence to substantiate the claim of the conjecture: the body-centered-cubic lattice (or Par6) based centroidal Voronoi tessellation has the lowest cost (or energy) per unit volume and is the most likely congruent cell predicted by the three-dimensional Gersho conjecture. More importantly, we probe the various properties of this optimal configuration including its dual triangulations which bear significant consequences in applications to three-dimensional high quality meshing.

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
PDF BibTeX Cite
Full Text: DOI
[1] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM review, 41, 637-676, (1999) · Zbl 0983.65021
[2] Du, Q.; Gunzburger, M., Grid generation and optimization based on centroidal Voronoi tessellations, Applied and computational mathematics, 133, 591-607, (2002) · Zbl 1024.65118
[3] Du, Q.; Wang, D., Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations, Int. J. num. method. engrg., 56, 1355-1373, (2003) · Zbl 1106.74431
[4] Du, Q.; Gunzburger, M.; Ju, L., Meshfree, probabilistic determination of point sets and support regions for meshless computing, Comput. methods appl. mech. engrg., 191, 1349-1366, (2002) · Zbl 0993.65009
[5] Q. Du, M. Gunzburger, L. Ju and X. Wang, Centroidal Voronoi tessellation algorithms for image compression segmentation, (preprint).
[6] Hausner, A., Simulating decorative mosaics, (), 573-580
[7] Kanungo, T.; Mount, D.; Netanyahu, N.; Piatko, C.; Silverman, R.; Wu, A., An efficient k-means clustering algorithm: analysis and implementation, IEEE trans. pattern anal. machl intel., 24, 881-892, (2002)
[8] Gersho, A., Asymptotically optimal block quantization, IEEE trans. inform. theory, 25, 373-380, (1979) · Zbl 0409.94013
[9] Newman, D., The hexagon theorem, IEEE trans. infor. theory, 28, 137-139, (1982) · Zbl 0476.94006
[10] Barnes, E.S.; Sloane, N.J.A., The optimal lattice quantizer in three dimensions, SIAM J. algebraic discrete methods, 4, 30-41, (1983) · Zbl 0509.52010
[11] Gray, R.M.; Neuhoff, D.L., Quantization, IEEE trans. inform. theory, 44, 2325-2383, (1998) · Zbl 1016.94016
[12] Lloyd, S., Least square quantization in PCM, IEEE trans. infor. theory, 28, 129-137, (1982) · Zbl 0504.94015
[13] Q. Du, M. Emelianenko and L. Ju, Convergence properties of the Lloyd algorithm for computing the Centroidal Voronoi Tessellations, (preprint) · Zbl 1115.65017
[14] Shewchuk, J.R., Tetrahedral mesh generation by Delaunay refinement, (), 86-95
[15] Miller, G.L.; Talmor, D.; Teng, S.H.; Walkington, N., A Delaunay based numerical method for three dimensons: generation, formulation and partition, (), 683-692 · Zbl 0978.68575
[16] Q. Du, M. Gunzburger and L. Ju, Constrained centroidal Voronoi tessellations on general surfaces, SIAM J. Sci. Comp{\bf24} (5), 1499-1506. · Zbl 1036.65101
[17] Q. Du and D. Wang, Approximate Constrained centroidal Voronoi tessellation on surfaces and the application to surface mesh optimization, (preprint).
[18] Du, Q.; Gunzburger, M.; Ju, L., Probablistic methods for centroidal Voronoi tessellations and their parallel implementations, Journal of parallel computing, 28, 1477-1500, (2002) · Zbl 1014.68202
[19] MacQueen, J., Some methods for classification and analysis of multivariate observations, (), 281-297 · Zbl 0214.46201
[20] Jain, A.; Dubes, R., Algorithms for clustering data, (1988), Prentice Hall Berlin · Zbl 0665.62061
[21] Sloane, N.J.A.; Vaishampayan, V.A., A zador-like formula for quantizers based on periodic tilings, IEEE trans. infor. theory, 48, 3138-3140, (2002) · Zbl 1062.94018
[22] Conway, J.H.; Sloane, N.J.A., Voronoi regions of lattices, second moments of polytopes and quantization, IEEE trans. inform. theory, 28, 211-226, (1982) · Zbl 0495.94003
[23] Kusner, R.; Sullivan, J.M., Comparing the weaire-phelan equal-volume foam to Kelvin’s foam, Forma, 11, 233-242, (1996) · Zbl 1017.52502
[24] Sullivan, J.M., The geometry of bubbles and foams, (), 379-402
[25] Kashyap, N.; Neuhoff, D.L., On quantization with the weaire-phelan partition, IEEE trans. inform. thy., 47, 2538-2543, (2001) · Zbl 1018.94008
[26] Sullivan, J.M., New tetrahedrally close-packed structures, (), 111-119, Delft
[27] Weaire, D.; Phelan, R., A counter-example to Kelvin’s conjecture on minimal surfaces, Phil. mag. lett., 69, 2, 107-110, (1994) · Zbl 0900.52003
[28] Du, Q.; Wang, D., Boundary recovery for three dimensional conforming Delaunay triangulation, Computer methods in applied mechanics and engineering, 193, 2547-2563, (2003) · Zbl 1063.65135
[29] Du, Q.; Wang, D., Constrained boundary recovery for three dimensional Delaunay triangulations, Int. J. num. method engrg., 61, 1471-1500, (2004) · Zbl 1073.65511
[30] Radovitzky, R.; Ortiz, M., Tetrahedral mesh generation based on node insertion in crystal lattice arrangment and advancing-front-Delaunay triangulation, Comput. methods appl. mech. engrg., 187, 543-569, (2000) · Zbl 0980.74080
[31] Molino, N.; Bridson, R.; Teran, J.; Fedkiw, R., A crystalline, red Green strategy for meshing highly deformable objects with tetrahedra, (), 103-114
[32] Eppstein, D.; Sullivan, J.M.; Üngör, A., Tiling space and slabs with acute tetrahdra, Computational geometry: theory and applications, 27, 237-255, (2004) · Zbl 1054.65020
[33] Kasper, J.; Hagenmuller, P.; Pouchard, M.; Cros, C., Clathrate structure of silicon na8si46 and na8si136(x < 11), Science, 150, 1713-1714, (1965)
[34] Frey, P.J., About surface remeshing, (), 123-156
[35] D. Wang, O. Hassan, K. Morgan and N.P. Weatherill, Surface grid generation based on remeshing, (preprint). · Zbl 1122.76074
[36] Q. Du and D. Wang, Optimal 3D tetrahedral meshing based on the optimal CVT, (preprint).
[37] Li, X.Y., Sliver-free three dimensional Delaunay mesh generation, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.