Research On Fast Generation Methods Of Power Diagram

As an extension of Voronoi diagram, power diagram has extensive applications. By imposing capacity or centroid constraints to the ordinary power diagram, centroidal or capacity constrained power diagram can be obtained. There are some existing algorithms to generate capacity constrained power diagram (CCPD), however, all of them can’t take into account both the time performances and accuracy. This dissertation focuses on the algorithm of fast generation power diagram.The main works of this dissertation are as follows:(1) Research progress of Voronoi diagram and power diagram is summarized, and the advantage and disadvantage of two certain generation algorithms for CCPD are analyzed;(2) A precise generation algorithm for CCPD is proposed. By using the analytical relationship of weight and capacity, the iterated weight increment can be accurately solved to eventually generate the required power diagram. By comparing with the previous generation algorithm and Balzer’s method, it can be concluded that the proposed method has faster generation speed, higher precision and better adaptability.(3) A novel method to generate fixed-site CCCPD under the constant density was proposed. The centroid of power cell was optimized by revising the weight of neighbor sites, and then the capacity of site was optimized by scaling the power cell in equal proportions. The two process are conducted alternately and iteratively in order to generate the fixed-site power diagram.