Centroidal Voronoi Tessellation with Local Optimization

doi:10.16182/j.issn1004731x.joss.17DEA-010

Abstract

Abstract: Centroidal Voronoi tessellation is a special geometric structure, which has many applications in various fields such as geographical information system, signal processing, mesh generation/optimization, visualization and so on. Due to the highly non-convex nature of the CVT energy function, the existing methods for computing CVT have several drawbacks, which always trap into local minima. We propose generation optimization and stochastic optimization schemes for further reducing the CVT energy. Experimental results show that the proposed method improves both quality and efficiency compared to the recent approaches.

Key words: centroidal Voronoi tessellation, local minimum, optimization, irregular point

CLC Number:

TP301

Ye Tianyu, Wang Yiqun, Yan Dongming, Yong Junhai. Centroidal Voronoi Tessellation with Local Optimization[J]. Journal of System Simulation, 2019, 31(2): 218-226.

References

[1] Du Q, Faber V, Gunzburger M.Centroidal Voronoi tessellations: Applications and algorithms[J]. SIAM review,(S0036-1445), 1999, 41(4): 637-676.
[2] Du Q, Gunzburger M.Grid generation and optimization based on centroidal Voronoi tessellations[J]. Applied Mathematics and Computation (S0096-3003), 2002, 133(2/3): 591-607.
[3] Du Q, Gunzburger M D, Ju L.Constrained centroidal Voronoi tessellations for surfaces[J]. SIAM Journal on Scientific Computing (S1064-8275), 2003, 24(5): 1488-1506.
[4] Lloyd S.Least squares quantization in PCM[J]. IEEE transactions on information theory (S0018-9448), 1982, 28(2): 129-137.
[5] Du Q, Emelianenko M, Ju L.Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations[J]. SIAM journal on numerical analysis (S0036-1429), 2006, 44(1): 102-119.
[6] Liu Y, Wang W, Lévy B, et al.On centroidal Voronoi tessellation—energy smoothness and fast computation[J]. ACM Transactions on Graphics (ToG)(S0730-0301), 2009, 28(4): 101.
[7] Lu L, Sun F, Pan H, et al.Global optimization of centroidal voronoi tessellation with monte carlo approach[J]. IEEE transactions on visualization and computer graphics (S1077-2626), 2012, 18(11): 1880-1890.
[8] Wang L, Hétroy-Wheeler F, Boyer E.A hierarchical approach for regular centroidal Voronoi tessellations[J] Computer Graphics Forum (S0167-7055), 2016, 35(1): 152-165.
[9] Du Q, Gunzburger M, Ju L.Advances in studies and applications of centroidal Voronoi tessellations[J]. Numerical Mathematics: Theory, Methods and Applications (S1004-8979), 2010, 3(2): 119-142.
[10] Gersho A.Asymptotically optimal block quantization[J]. IEEE Transactions on information theory,(S0018-9448), 1979, 25(4): 373-380.
[11] Fejes Tóth G.A stability criterion to the moment theorem[J]. Studia Scientiarum Mathematicarum Hungarica (S0081-6906), 2001, 38(1/2/3/4): 209-224.
[12] Asami Y."A Note on the Derivation of the First and Second Derivatives of Objective Functions in Geographical Optimization Problems", Journal of Faculty of Engineering, University of Tokyo[J], 1991, 61(1), 1-13.
[13] Iri M, Murota K, Ohya T.A fast Voronoi-diagram algorithm with applications to geographical optimization problems[M] Berlin, Heidelberg: System modelling and optimization. Springer , 1984: 273-288.
[14] Du Q, Emelianenko M.Acceleration schemes for computing centroidal Voronoi tessellations[J]. Numerical linear algebra with applications (S1070-5325), 2006, 13(2/3): 173-192.
[15] CGAL, Computational Geometry Algorithms Library. http://www.cgal.org.
[16] Yan D M, Wang K, Lévy B, et al.Computing 2D periodic centroidal Voronoi tessellation[C]// Voronoi Diagrams in Science and Engineering (ISVD), 2011 Eighth International Symposium on. IEEE, 2011: 177-184.