Integrated Generating Algorithm of Centroidal Capacity Constrained Power Diagram

doi:10.16182/j.issn1004731x.joss.201807008

Abstract

Abstract: Power diagram is the weighted Voronoi diagram. Centroidal capacity constrained power diagram (CCCPD) can be obtained by imposing capacity constraint and centroid constraint to the ordinary power diagram. To increase the convergence speed of existing CCCPD algorithms which optimize the weight and location of site interlacedly, an improved algorithm is proposed which optimizes all variables integratedly. Research results exhibit that the performance of the proposed algorithm is 40% higher than the traditional method.

Key words: power diagram, capacity constrained, centroidal, fast computing

CLC Number:

TP391.1

Zheng Liping, Lu Chang, Cai Ruiwen, Gui Zhiqiang. Integrated Generating Algorithm of Centroidal Capacity Constrained Power Diagram[J]. Journal of System Simulation, 2018, 30(7): 2489-2496.

References

[1] Balzer M, Schlömer T, Deussen O.Capacity- Constrained Point Distributions:A Variant of Lloyd's Method[J]. ACM Transactions on Graphics (S0730-0301), 2009, 28(3): 86.
[2] De Goes F, Breeden K, Ostromoukhov V, et al.Blue noise through optimal transport[J]. ACM Transactions on Graphics (S0730-0301), 2012, 31(6): 567-571.
[3] 郑利平, 程亚军, 周乘龙, 等. 异构群体队形光滑变换控制方法[J]. 计算机辅助设计与图形学学报, 2015, 27(10): 1963-1970.
Zheng Li-Ping, Cheng Ya-Jun, Zhou Cheng-Long, et al.Research on Smooth Formation Control of Heterogeneous Crowds[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(10): 1963-1970.
[4] Mridul Aanjaneya, Ming Gao, Haixiang Liu, et al.Power diagrams and sparse paged grids for high resolution adaptive liquids[J]. ACM Transactions on Graphics(S0730-0301), 2017, 36(4): 140.
[5] 郑利平, 江婷, 周乘龙, 等. 基于Power图求解容量限制P-中值问题[J]. 计算机应用, 2015, 35(6): 1623-1627.
Zheng Li-Ping, Jiang Ting, Zhou Cheng-Long, et al.Solving approach of capacity constrained P-median problem based on Power diagram[J]. Journal of Computer Applications, 2015, 35(6): 1623-1627.
[6] 郑利平, 刘玉飞, 江婷, 等. 稠密需求下城市应急中心布局方法[J]. 计算机辅助设计与图形学学报, 2014, 26(6): 948-955.
Zheng Li-Ping, Liu Yu-fei, Jiang Ting, et al.A Layout Approach of City Emergency Centers with Dense Demand[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(6): 948-955.
[7] Borgwardt S.On Soft Power Diagrams[J]. Journal of Mathematical Modelling and Algorithms in Operations Research (S2214-2487), 2015, 14(2): 173-196.
[8] G Barlow.Hexagonal territories[J]. Animal Behav (S0003-3472), 1974(22): 876-878.
[9] 郑利平, 程亚军, 路畅, 等. 质心Power图下覆盖路径规划算法[J]. 系统仿真学报, 2017, 29(5): 1120-1124.
Zheng Liping, Cheng Yajun, Lu Chang, et al.Coverage Path Planning Algorithm Based on Centroidal Power Diagram[J]. Journal of System Simulation, 2017, 29(5): 1120-1124.
[10] Aurenhammer F.Voronoi diagram-A survey of a fundamental geometry data structure[J]. ACM Computing Surveys(S0360-0300), 1991, 23(3): 345-405.
[11] Aurenhammer F.Power diagrams: properties, algorithms and applications[J]. SIAM Journal on Computing (S0097-5397), 1987, 16(1): 78-96.
[12] H Imai, M Iri, K Murota.Voronoi diagram in the Laguerre geometry and its application[J]. SIAM Journal on Computing(S0097-5397), 1985, 14(1): 93-105.
[13] Balzer Michael, Daniel Heck.Capacity-constrained Voronoi diagrams in finite spaces[C]//Proceedings of the 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering, Voronoi’s Impact on Modern Science, 2008, 4(2): 44-56.
[14] Balzer M.Capacity-constrained Voronoi diagrams in continuous spaces[C]. ISVD, 2009: 79-88.
[15] 江婷. 容量限制Power 图的快速生成及其应用[D]. 合肥: 合肥工业大学, 2015.
Jiang Ting.A Rapid Generating Method of Capacity Constrained Power Diagram and Its Applications [D]. Hefei: Hefei University of Technology, 2015.
[16] Xin S Q, Vy B, Chen Z, et al.Centroidal power diagrams with capacity constraints: computation, applications, and extension[J]. ACM Transactions on Graphics (S0730-0301), 2016, 35(6): 1-12.