姚裕友，张高峰，徐本柱，郑利平

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

姚裕友，张高峰，徐本柱，郑利平

(合肥工业大学计算机与信息学院，安徽 合肥 230601)

Power图作为Voronoi图的拓展，引入“权重”使其有着良好的限容特性。对普通Power图增加容量约束，使得每个站点的容量等于预设的容量值，则可以得到容量限制Power图；在此基础上，再增加质心约束，使每个站点刚好位于对应Power区域的质心，进一步得到质心容量限制Power图。在质心容量限制Power图中，容量限制条件均有明确的值，然而在某些应用中其往往是一个区间。针对区间容量限制问题，提出一种变容量限制质心Power图的计算方法。一方面，该方法通过不断调整各站点的权重以使得站点的容量满足区间限制；另一方面，Lloyd方法被用于优化各站点的位置到对应Power区域的质心；两者交替迭代优化，从而得到满足区间容量限制的质心Power图。在不同的密度和不同容量限制区间下的实验结果表明，该方法适用于不同密度下变容量限制质心Power图的计算，并且具有高效、适应性强等优点。

Power图；变容量限制；区间；质心；密度

在计算几何中，Voronoi图作为一种基础的几何结构有着广泛地应用与拓展。DU等[1]在普通的Voronoi图的基础上约束站点至质心位置，得到基于质心的Voronoi图(centroidal Voronoi tessellation，CVT)；郑利平等[2]在CVT的基础上引入容量限制，得到容量限制的质心Voronoi图(capacity constrained centroidal Voronoi tessellation，CCCVT)，并将其应用于城市选址布局问题中。然而Voronoi图因其得到的剖分过于刚性，难以满足容量限制要求。

AURENHAMMER等[3]对Voronoi图进行拓展得到Power图，Power图通过控制每个站点的权重值来控制站点的容量，从而弱化了Voronoi图的刚性限制。……