Efficient Computation Method of Capacity Constrained Power Diagram

Comparing with Voronoi diagram,power diagram has the useful characteristics of precise capacity holding,thus it can be applied in many fields.Capacity constrained power diagram(CCPD)can be obtained by imposing capacity constraint to the ordinary power diagram by adding a weight to each site.However,power diagram computation is hard and complex due to its high time complexity.In this paper,we firstly prove the monotonicity of power diagram weight against capacity theoretically,and then based on Balzer’s method,we present an improved and fast analytic algorithm to directly calculate power weights instead of the counterpart false position method.Experiment results exhibit that proposed algorithm has the advantages of good efficiency,high accuracy,easy to implementation,and strong adaptability for complex density fields.