变容量限制质心Power图的计算  

Computation method of variable capacity constrained centroidal Power diagram

作　　者：姚裕友 张高峰[1] 徐本柱[1] 郑利平[1] YAO Yu-you;ZHANG Gao-feng;XU Ben-zhu;ZHENG Li-ping(School of Computer Science and Information Engineering,Hefei University of Technology,Hefei Anhui 230601,China)

机构地区：[1]合肥工业大学计算机与信息学院,安徽合肥230601

出　　处：《图学学报》2021年第3期492-500,共9页Journal of Graphics

基　　金：国家自然科学基金项目(61972128,61702155)。

摘　　要：Power图作为Voronoi图的拓展,引入“权重”使其有着良好的限容特性。对普通Power图增加容量约束,使得每个站点的容量等于预设的容量值,则可以得到容量限制Power图;在此基础上,再增加质心约束,使每个站点刚好位于对应Power区域的质心,进一步得到质心容量限制Power图。在质心容量限制Power图中,容量限制条件均有明确的值,然而在某些应用中其往往是一个区间。针对区间容量限制问题,提出一种变容量限制质心Power图的计算方法。一方面,该方法通过不断调整各站点的权重以使得站点的容量满足区间限制;另一方面,Lloyd方法被用于优化各站点的位置到对应Power区域的质心;两者交替迭代优化,从而得到满足区间容量限制的质心Power图。在不同的密度和不同容量限制区间下的实验结果表明,该方法适用于不同密度下变容量限制质心Power图的计算,并且具有高效、适应性强等优点。The Power diagram,as an extension of the Voronoi diagram,introduces“weight”to each site,and is characteristic of accurate tolerance.By imposing the capacity constraints to the ordinary Power diagram,a capacity-constrained Power diagram can be obtained,where the capacity of each site equates to the preset capacity constraint.The addition of the centroid constraints on a secondary basis can lead to the centroidal capacity-constrained Power diagram,in which the sites are located at its mass centers of the corresponding Power cells.In these Power diagrams,the capacity constraints are clear values.However,the capacity constraints are often intervals in some practical applications.To address this problem,a computation method was proposed for variable capacity-constrained centroidal Power diagram.On the one hand,the method can continuously update the weights of sites to meet the capacity constraints.On the other hand,the Lloyd’s method is applied to the relocation of the sites to its mass centers of the corresponding Power cells.The two steps interfere with each other in the optimization process to compute the centroidal Power diagram with interval capacity constraints.The experimental results demonstrate that the proposed method can stably compute the variable capacity-constrained centroidal Power diagram under different conditions with the advantages in high efficiency and adaptability.

关 键 词：Power图 变容量限制 区间 质心 密度 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]