A novel computation method of hybrid capacity constrained centroidal power diagram

Abstract Power diagrams, as a powerful extension of Voronoi diagrams, have been utilized in a wide range of applications in various fields. By imposing the capacity constraint and the centroid constraint to the ordinary power diagram, capacity-constrained power diagram and centroidal capacity-constrained power diagram can be obtained respectively, in which, all the capacity constraints are fixed values. However, some practical applications require a special kind of power diagrams, called hybrid capacity-constrained centroidal power diagrams, where not all capacity constraints are fixed values, and instead there are some capacities of sites constrained to intervals. To this end, we propose an iterative computation method for the power diagrams with hybrid capacity constraints. On the one hand, a weight evaluated method is introduced to update the weights of interval capacity-constrained sites, and Newton’s method is applied to optimize the weights of fixed-value capacity-constrained sites. On the other hand, Lloyd’s method is employed to move the sites to their respective mass centers. Experimental results prove that the proposed method can effectively compute the centroidal power diagram with hybrid capacity constraints.