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

Abstract: 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. 

Key words:  , Power diagram, variable capacity-constrained, interval, centroidal, density