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

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

Computation method of variable capacity constrained centroidal Power diagram

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.