基于局部优化的重心Voronoi图计算

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

系统仿真学报 ›› 2019, Vol. 31 ›› Issue (2): 218-226.doi: 10.16182/j.issn1004731x.joss.17DEA-010

基于局部优化的重心Voronoi图计算

叶畋宇¹, 王逸群², 严冬明^{2, *}, 雍俊海¹

1. 清华大学软件学院,北京 100084;
2. 中国科学院自动化研究所模式识别国家重点实验室,北京 100190

收稿日期:2016-10-12 修回日期:2017-01-30 出版日期:2019-02-15 发布日期:2019-02-15
作者简介:叶畋宇(1990-),男,上海,博士生,研究方向为计算机辅助几何设计。
基金资助:
国家科技支撑计划(2015BAF23B03), 国家国际科技合作专项(2013DFE13120), 国家自然科学基金(61772523, 61272235, 61372168, 61672307)

Centroidal Voronoi Tessellation with Local Optimization

Ye Tianyu¹, Wang Yiqun², Yan Dongming^{2, *}, Yong Junhai¹

1. School of Software, Tsinghua University, Beijing 100084, China;
2. NLPR, Insistute of Automation, Chinese Academy of Sciences, Beijing 100190, China

Received:2016-10-12 Revised:2017-01-30 Online:2019-02-15 Published:2019-02-15

摘要/Abstract

摘要： 重心Voronoi图(centroidal Voronoi tessellation,CVT)是一个重要的几何结构,在地理信息系统,信号处理,网格生成/优化,可视化等领域有着重要应用。针对传统全局生成、优化的方法的不足,比如奇异点多、收敛速度较慢等问题,提出了生成优化与随机扰动两种局部优化方法,以及一个整合了层次生成、局部优化、蒙特卡罗优化的CVT生成算法框架。实验结果表明,相比于已有算法,本文方法在速度与质量上有综合的提升。

关键词: 重心Voronoi图, 局部极小, 优化, 奇异点

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

中图分类号:

TP301

叶畋宇, 王逸群, 严冬明, 雍俊海. 基于局部优化的重心Voronoi图计算[J]. 系统仿真学报, 2019, 31(2): 218-226.

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

参考文献

[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.

基于局部优化的重心Voronoi图计算

Centroidal Voronoi Tessellation with Local Optimization

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	李智杰, 石昊琦, 李昌华, 张颉. 基于改进遗传算法的影像中心布局优化方法[J]. 系统仿真学报, 2022, 34(6): 1173-1184.
[2]	段绍米, 罗会龙, 刘海鹏. 人群搜索和樽海鞘群的混合算法优化PID参数[J]. 系统仿真学报, 2022, 34(6): 1230-1246.
[3]	张其文, 张斌. 基于教学优化算法求解置换流水车间调度问题[J]. 系统仿真学报, 2022, 34(5): 1054-1063.
[4]	古鹏飞, 张霖, 陈真, 叶俊杰. 基于X语言的起飞场景民机协同设计与仿真一体化方法[J]. 系统仿真学报, 2022, 34(5): 929-943.
[5]	叶澍, 吉晓东, 李文华. 全双工无人机中继系统物理层安全性能研究[J]. 系统仿真学报, 2022, 34(4): 788-796.
[6]	高鑫宇, 倪静. 救援效率视角下灾后动态应急配送网络优化[J]. 系统仿真学报, 2022, 34(4): 806-816.
[7]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
[8]	叶飞, 李梓晴, 赖李媛君. 分布式车间生产维修联合调度仿真优化方法[J]. 系统仿真学报, 2022, 34(4): 688-699.
[9]	冯开团, 袁杰. 基于改进注水算法的离散车间任务分配问题研究[J]. 系统仿真学报, 2022, 34(4): 768-776.
[10]	李建锋, 卢迪, 李贺香. 一种改进的原子搜索算法[J]. 系统仿真学报, 2022, 34(3): 490-502.
[11]	董君, 叶春明. 半导体晶圆节能分布式制造与预维护联合优化[J]. 系统仿真学报, 2022, 34(3): 584-602.
[12]	杨敬辉, 刘德康, 杜万和, 邢立宁. 基于图像特征的双目测距系统的研究[J]. 系统仿真学报, 2022, 34(3): 624-632.
[13]	王红微, 杨鹏. 基于深度强化学习的机场货运业务优化研究[J]. 系统仿真学报, 2022, 34(3): 651-660.
[14]	张子伟, 郭齐胜, 董志明, 高昂, 王艺霏. 体系作战效能评估与优化方法综述[J]. 系统仿真学报, 2022, 34(2): 303-313.
[15]	许斌, 闫文卿, 韩卓凡, 何广深, 邓涛, 赵云凯, 亓晋. 基于烟花算法的基站群协作计算卸载模型研究[J]. 系统仿真学报, 2022, 34(2): 354-365.