A novel computation method of hybrid capacity constrained centroidal power diagram. (June 2021)

• Record Type: Journal Article
• Authors: Zheng, Liping; Yao, Yuyou; Wu, Wenming; Xu, Benzhu; Zhang, Gaofeng
• Is Part Of: Computers & graphics. Volume 97(2021)
• Page Start: 108
• Page End: 116
• Publication Date: 2021-06
• Subjects: Power diagram -- Hybrid capacity constraints -- Centroidal -- Density; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2021.04.007
• Languages: English
• ISSNs: 0097-8493

Abstract

Highlights: A centroidal power diagram with hybrid capacity constraints is introduced. We proposed a method to optimize the weights of variable capacity-constrained sites. Our computation method is coupled with Newton's method and Lloyd's method. The HCCCPD algorithm is employed to solve the location-allocation problem. Graphical abstract: 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.