A simple geometric method for navigating the energy landscape of centroidal Voronoi tessellations. (English) Zbl 1467.49033
Summary: Finding optimal (or low energy) centroidal Voronoi tessellations (CVTs) on a two-dimensional domain is a challenging problem. One must navigate an energy landscape whose desirable critical points have sufficiently small basins of attractions that are inaccessible with Monte Carlo initialized gradient descent methods. We present a simple deterministic method for efficiently navigating the energy landscape in order to access these low energy CVTs. The method has two parameters and is based upon each generator moving away from the closest neighbor by a certain distance. We give a statistical analysis of the performance of this hybrid method comparing with the results of a large number of runs for both Lloyd’s method and state-of-the-art quasi-Newton methods. Stochastic alternatives are also considered.
MSC:
| 49Q10 | Optimization of shapes other than minimal surfaces |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
centroidal Voronoi tessellation; global optimization; energy ground state; optimal vector quantizer; regularity measuresSoftware:
CGALReferences:
| [1] | P. Alliez, D. Cohen-Steiner, M. Yvinec, and M. Desbrun, Variational tetrahedral meshing, ACM Trans. Graph., 24 (2005), pp. 617-625. |
| [2] | E. S. Barnes and N. J. A. Sloane, The optimal lattice quantizer in three dimensions, SIAM J. Algebraic Discrete Methods, 4 (1983), pp. 30-41, https://doi.org/10.1137/0604005. · Zbl 0509.52010 |
| [3] | X. Blanc and M. Lewin, The crystallization conjecture: A review, EMS Surv. Math. Sci., 2 (2015), pp. 225-306. · Zbl 1341.82010 |
| [4] | E. Bormashenko, M. Frenkel, and I. Legchenkova, Is the Voronoi entropy a true entropy? Comments on “Entropy, Shannon”s measure of information and Boltzmann’s H-theorem,” Entropy 2017, 19, 48, Entropy, 21 (2019), 251. |
| [5] | E. Bormashenko, M. Frenkel, A. Vilk, I. Legchenkova, A. A. Fedorets, N. E. Aktaev, L. A. Dombrovsky, and M. Nosonovsky, Characterization of self-assembled \(2\) D patterns with Voronoi entropy, Entropy, 20 (2018), 956. |
| [6] | M. Caroli and M. Teillaud, Computing \(3\) D periodic triangulations, in Algorithms-ESA 2009, Lecture Notes in Comput. Sci. 5757, Springer, Berlin, 2009, pp. 59-70. · Zbl 1256.68147 |
| [7] | J. Chen, D. Wang, and Q. Du, Linear finite element superconvergence on simplicial meshes, Math. Comp., 83 (2014), pp. 2161-2185. · Zbl 1312.65187 |
| [8] | L. Chen and J.-c. Xu, Optimal Delaunay triangulations, J. Comput. Math., 22 (2004), pp. 299-308. · Zbl 1048.65020 |
| [9] | R. Choksi and X. Y. Lu, Bounds on the geometric complexity of optimal centroidal Voronoi tesselations in 3D, Comm. Math. Phys., 377 (2020), pp. 2429-2450. · Zbl 1443.52021 |
| [10] | P. N. Chung, M. A. Fernandez, N. Shah, L. S. Vieira, and E. Wikner, Perimeter-minimizing pentagonal tilings, Involve, 7 (2014), pp. 453-478. · Zbl 1301.52036 |
| [11] | J. Conway and N. Sloane, Voronoi regions of lattices, second moments of polytopes, and quantization, IEEE Trans. Inform. Theory, 28 (1982), pp. 211-226. · Zbl 0495.94003 |
| [12] | Q. Du and M. Emelianenko, Acceleration schemes for computing centroidal Voronoi tessellations, Numer. Linear Algebra Appl., 13 (2006), pp. 173-192. · Zbl 1174.05323 |
| [13] | Q. Du, M. Emelianenko, and L. Ju, Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations, SIAM J. Numer. Anal., 44 (2006), pp. 102-119, https://doi.org/10.1137/040617364. · Zbl 1115.65017 |
| [14] | Q. Du, V. Faber, and M. Gunzburger, Centroidal Voronoi tessellations: Applications and algorithms, SIAM Rev., 41 (1999), pp. 637-676, https://doi.org/10.1137/S0036144599352836. · Zbl 0983.65021 |
| [15] | Q. Du, M. Gunzburger, and L. Ju, Advances in studies and applications of centroidal Voronoi tessellations, Numer. Math. Theory Methods Appl., 3 (2010), pp. 119-142. · Zbl 1224.52032 |
| [16] | Q. Du and D. Wang, The optimal centroidal Voronoi tessellations and the Gersho’s conjecture in the three-dimensional space, Comput. Math. Appl., 49 (2005), pp. 1355-1373. · Zbl 1077.65019 |
| [17] | M. Emelianenko, Fast multilevel CVT-based adaptive data visualization algorithm, Numer. Math. Theory Methods Appl., 3 (2010), pp. 195-211. · Zbl 1224.65050 |
| [18] | M. Emelianenko, L. Ju, and A. Rand, Nondegeneracy and weak global convergence of the Lloyd algorithm in \(\mathbb{R}^d\), SIAM J. Numer. Anal., 46 (2008), pp. 1423-1441, https://doi.org/10.1137/070691334. · Zbl 1171.65012 |
| [19] | A. Gersho, Asymptotically optimal block quantization, IEEE Trans. Inform. Theory, 25 (1979), pp. 373-380. · Zbl 0409.94013 |
| [20] | S. Graf and H. Luschgy, Foundations of Quantization for Probability Distributions, Lecture Notes in Math. 1730, Springer-Verlag, Berlin, 2000. · Zbl 0951.60003 |
| [21] | P. M. Gruber, A short analytic proof of Fejes Tóth’s theorem on sums of moments, Aequationes Math., 58 (1999), pp. 291-295. · Zbl 1006.52015 |
| [22] | W. W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods, Pac. J. Optim., 2 (2006), pp. 35-58. · Zbl 1117.90048 |
| [23] | J. H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math., 2 (1960), pp. 84-90. · Zbl 0090.34505 |
| [24] | J. M. Hammersley, Monte Carlo methods for solving multivariable problems, Ann. New York Acad. Sci., 86 (1960), pp. 844-874. · Zbl 0111.12405 |
| [25] | J. C. Hateley, H. Wei, and L. Chen, Fast methods for computing centroidal Voronoi tessellations, J. Sci. Comput., 63 (2015), pp. 185-212. · Zbl 1328.62386 |
| [26] | M. Iri, K. Murota, and T. Ohya, A fast Voronoi-diagram algorithm with applications to geographical optimization problems, in System Modelling and Optimization, Lect. Notes Control Inf. Sci. 59, Springer, Berlin, 1984, pp. 273-288. · Zbl 0557.90025 |
| [27] | L. Jiang, R. H. Byrd, E. Eskow, and R. B. Schnabel, A Preconditioned L-BFGS Algorithm with Application to Molecular Energy Minimization, Tech. report, Department of Computer Science, University of Colorado at Boulder, Boulder, CO, 2004. |
| [28] | L. Ju, Q. Du, and M. Gunzburger, Probabilistic methods for centroidal Voronoi tessellations and their parallel implementations, Parallel Comput., 28 (2002), pp. 1477-1500. · Zbl 1014.68202 |
| [29] | Z. Li and H. A. Scheraga, Monte Carlo-minimization approach to the multiple-minima problem in protein folding, Proc. Nat. Acad. Sci. U.S.A., 84 (1987), pp. 6611-6615. |
| [30] | C.-J. Lin and J. J. Moré, Incomplete Cholesky factorizations with limited memory, SIAM J. Sci. Comput., 21 (1999), pp. 24-45, https://doi.org/10.1137/S1064827597327334. · Zbl 0941.65033 |
| [31] | Y. Liu, W. Wang, B. Lévy, F. Sun, D.-M. Yan, L. Lu, and C. Yang, On centroidal Voronoi tessellation-energy smoothness and fast computation, ACM Trans. Graph., 28 (2009), 101. |
| [32] | S. Lloyd, Least squares quantization in PCM, IEEE Trans. Inform. Theory, 28 (1982), pp. 129-137. · Zbl 0504.94015 |
| [33] | L. Lu, F. Sun, H. Pan, and W. Wang, Global optimization of centroidal Voronoi tessellation with Monte Carlo approach, IEEE Trans. Vis. Comput. Graph., 18 (2012), pp. 1880-1890. |
| [34] | T. McSweeney, Modified Cholesky Decomposition and Applications, Master’s thesis, University of Manchester, Manchester, UK, 2017. |
| [35] | Y. Men, Z. Shen, D. Khan, and D.-M. Yan, Improving regularity of the centoridal Voronoi tessellation, in SIGGRAPH ’18: ACM SIGGRAPH 2018 Posters, ACM, 2018, 66. |
| [36] | M. Moriguchi and K. Sugihara, A new initialization method for constructing centroidal Voronoi tessellations on surface meshes, in Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering, IEEE, 2006, pp. 159-165. |
| [37] | D. Newman, The hexagon theorem, IEEE Trans. Inform. Theory, 28 (1982), pp. 137-139. · Zbl 0476.94006 |
| [38] | H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, CBMS-NSF Regional Conf. Ser. in Appl. Math. 63, SIAM, 1992, https://doi.org/10.1137/ 1.9781611970081. · Zbl 0761.65002 |
| [39] | J. Nocedal and S. Wright, Numerical Optimization, 2nd ed., Springer, New York, 2006. · Zbl 1104.65059 |
| [40] | A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd ed., Wiley Ser. Probab. Stat. 501, John Wiley & Sons, Chichester, UK, 2009. · Zbl 0946.68144 |
| [41] | J. Quinn, F. Sun, F. C. Langbein, Y.-K. Lai, W. Wang, and R. R. Martin, Improved initialisation for centroidal Voronoi tessellation and optimal Delaunay triangulation, Comput.-Aided Des., 44 (2012), pp. 1062-1071. |
| [42] | The CGAL Project, CGAL User and Reference Manual, CGAL Editorial Board, 5.0 ed., 2019, https://doc.cgal.org/5.0/Manual/packages.html. |
| [43] | L. F. Tóth, Lagerungen in der Ebene auf der Kugel und im Raum, Springer-Verlag, Berlin, Göttingen, Heidelberg, 1953. · Zbl 0052.18401 |
| [44] | L. Wang, F. Hétroy-Wheeler, and E. Boyer, A hierarchical approach for regular centroidal Voronoi tessellations, Comput. Graph. Forum, 35 (2016), pp. 152-165. |
| [45] | D.-M. Yan, K. Wang, B. Lévy, and L. Alonso, Computing \(2\) D periodic centroidal Voronoi tessellation, in Proceedings of the Eighth International Symposium on Voronoi Diagrams in Science and Engineering, IEEE, 2011, pp. 177-184. |
| [46] | J. Zhang, M. Emelianenko, and Q. Du, Periodic centroidal Voronoi tessellations, Int. J. Numer. Anal. Model., 9 (2012), pp. 950-969. · Zbl 1267.65029 |
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.
