郑利平,郜文灿,李尚林,曹力(合肥工业大学计算机与信息学院, 合肥 230009)
目的 Power图作为Voronoi图的扩展，有着精确的限容特性。在普通Power图上添加容量限制即得到容量限制Power图。考虑站点位置固定情况，对于基于质心的容量限制Power图目前未有较好的计算方法。为了解决该类问题，提出一种新颖的常密度下的定点容量限制质心Power图生成算法。方法 通过调整站点的邻居站点的权值，优化该站点Power区域质心；在此基础上，按照相同比例缩放该站点Power区域，以达到优化容量的目的，最终生成所需Power图。结果 在综合考虑质心约束与容量限制条件下，对算法在均匀容量限制与非均匀容量限制下生成的Power图进行对比实验，并且分析实验误差。本文算法能够较好地解决容量限制问题，得到当前条件下的最优解。结论 本文算法在常密度下能稳定地生成容量限制质心Power图，具有精确度高和适应性强等优点。
Generation method for a centroidal capacity constrained Power diagram with fixed sites
Zheng Liping,Gao Wencan,Li Shanglin,Cao Li(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)
Objective As an extension of the Voronoi diagram, a power diagram possesses precise capacity holding characteristics. A capacity constrained power diagram (CCPD) can be obtained by imposing a capacity constraint on an ordinary power diagram. When the site is fixed, no efficient method to generate a centroidal CCPD (CCCPD) is available. Method A novel fixed-site method to generate CCCPD under constant density was proposed to solve this problem. The centroid of a power cell was optimized by revising the weight of its neighbor sites. Through this method, the capacity of the site was optimized by scaling the power cell in equal proportions, which eventually generated the required power diagram. Result This work considered centroid and capacity constraints to compare the converged power diagrams under uniform capacity constraint and non-uniform capacity constraint. The differences of the results of the experiments were then analyzed. On the basis of the analysis of the results, the proposed method could be concluded to be effective in solving the capacity constraint problem; it obtained an optimal solution under constraints. Conclusion Experiment results proved that the proposed method can stably generate CCCPD under a constant density with the advantages of high precision and good adaptability.