Bounds on the geometric complexity of optimal centroidal Voronoi tesselations in 3D. (English) Zbl 1443.52021
Summary: Gersho’s conjecture in 3D asserts the asymptotic periodicity and structure of the optimal centroidal Voronoi tessellation. This relatively simple crystallization problem remains to date open. We prove bounds on the geometric complexity of optimal centroidal Voronoi tessellations as the number of generators tends to infinity. Combined with an approach of Gruber in 2D, these bounds reduce the resolution of the 3D Gersho’s conjecture to a finite, albeit very large, computation of an explicit convex problem in finitely many variables.
MSC:
| 52C45 | Combinatorial complexity of geometric structures |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
asymptotic periodicity; geometric complexity; optimal centroidal Voronoi tessellations; 3D Gersho’s conjectureReferences:
| [1] | Barnes, ES; Sloane, NJA, The optimal lattice quantizer in three dimensions, SIAM J. Algebr. Discrete Methods, 4, 30-41 (1983) · Zbl 0509.52010 |
| [2] | Blanc, X.; Lewin, M., The crystallization conjecture: a review, EMS Surv. Math. Sci., 2, 2, 225-306 (2015) · Zbl 1341.82010 |
| [3] | Bourne, D.P., Schmitzer, B., Wirth, B.: Semi-discrete unbalanced optimal transport and quantization. Preprint (2018) |
| [4] | Cohn, H.; Kumar, A.; Miller, SD; Radchenko, D.; Viazovska, MS, The sphere packing problem in dimension 24, Ann. Math. (2), 183, 3, 1017-1033 (2017) · Zbl 1370.52037 |
| [5] | Cohn H., Kumar A., Miller S.D., Radchenko D., Viazovska, M.S.: Universal optimality of the \(E_8\) and Leech lattices and interpolation formulas. https://arxiv.org/pdf/1902.05438.pdf |
| [6] | Conway, JH; Sloane, NJA, Sphere Packings, Lattices and Groups, Grundlehren der Mathematischen Wissenschaften (1998), Berlin: Springer, Berlin |
| [7] | Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev., 41, 4, 637-676 (1999) · Zbl 0983.65021 |
| [8] | Du, Q.; Wang, D., The optimal centroidal Voronoi tessellations and the Gersho’s conjecture in the three-dimensional space, Comput. Math. Appl., 49, 1355-1373 (2005) · Zbl 1077.65019 |
| [9] | Dwyer, RA, The expected number of \(k\)-faces of a Voronoi diagram, Comput. Math. Appl., 26-5, 13-19 (1993) · Zbl 0781.60015 |
| [10] | Weinan, E.; Li, D., On the crystallization of 2D hexagonal lattices, Commun. Math. Phys., 286, 3, 1099-1140 (2009) · Zbl 1180.82191 |
| [11] | Farmer, B.; Esedoglu, S.; Smereka, P., Crystallization for a Brenner-like potential, Commun. Math. Phys., 349, 3, 1029-1061 (2017) · Zbl 1381.74044 |
| [12] | Fejes Tóth, G., Lagerungen in der Ebene, auf der Kugel und im Raum (1972), Berlin: Springer, Berlin · Zbl 0052.18401 |
| [13] | Flatley, LC; Theil, F., Face-centered cubic crystallization of atomistic configurations, Arch. Ration. Mech. Anal., 218, 1, 363-416 (2015) · Zbl 1335.82006 |
| [14] | Gersho, A., Asymptotically optimal block quantization, IEEE Trans. Inform. Theory, 25, 373-380 (1979) · Zbl 0409.94013 |
| [15] | Gruber, PM, A short analytic proof of Fejes Toth’s theorem on sums of moments, Aequ. Math., 58, 291-295 (1999) · Zbl 1006.52015 |
| [16] | Gruber, PM, Optimum quantization and its applications, Adv. Math., 186, 456-497 (2004) · Zbl 1062.94012 |
| [17] | Gruber, PM, Convex and Discrete Geometry, Springer Grundlehren der Mathematischen Wissenschaften (2007), Berlin: Springer, Berlin · Zbl 1139.52001 |
| [18] | Hales, TC, The Honeycomb conjecture, Discrete Comput. Geom., 25-1, 1-22 (2001) · Zbl 1007.52008 |
| [19] | Heitmann, RC; Radin, C., The ground state for sticky discs, J. Stat. Phys., 33, L804 (1994) |
| [20] | Newman, DJ, The hexagon theorem, IEEE Trans. Inform. Theory, 28, 137-139 (1982) · Zbl 0476.94006 |
| [21] | Radin, C., Low temperature and the origin of crystal symmetry, Int. J. Mod. Phys. B, 1, 1157-1191 (1987) |
| [22] | Ruelle, D., Statistical Mechanics: Rigorous Results (1999), Singapore: World Scientific Publishing, Singapore · Zbl 1016.82500 |
| [23] | Theil, F., A proof of crystallization in two dimensions, Commun. Math. Phys., 262, 1, 209-236 (2006) · Zbl 1113.82016 |
| [24] | Viazovska, MS, The sphere packing problem in dimension 8, Ann. Math. (2), 183, 3, 991-1015 (2017) · Zbl 1373.52025 |
| [25] | Villani, C., Optimal Transport. Old and New, Grundlehren der Mathematischen Wissenschaften (2009), Berlin: Springer, Berlin · Zbl 1156.53003 |
| [26] | Weaire, D.; Phelan, R., A counter-example to Kelvin’s conjecture on minimal surfaces, Philos. Mag. Lett., 69, 2, 107-110 (1994) · Zbl 0900.52003 |
| [27] | Zador, PL, Asymptotic quantization error of continuous signals and the quantization dimension, IEEE Trans. Inform. Theory, 28, 139-148 (1982) · Zbl 0476.94008 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
