Research On Computation Algorithm Of Power Diagram Based On GPU

As an extension of Voronoi diagram,power diagram has extensive applications.By imposing capacity constrains and centroid restriction to the Power diagram,CCCPD can be obtained.The existing generation of CCCPD algorithms are often based on the CPU's,they are difficult to meet the requirements of computing real-time large-scale sites in fast speed.Thus,this dissertation imports GPU to speed up the process of generating Power diagram,and research related algorithms.The main works of this dissertation are as follows:1)Research progress and computation algoritnms of Voronoi diagram,Power diagram and GPU accelerated Voronoi diagram are summarized.2)A pure GPU acceleration algorithm for Power diagram is proposed.Firstly GPU acceleration generates Power diagram;Secondly,GPU acceleration optimizes capacity constrains and centroid restriction.Then GPU acceleration generates CCCPD.Experiments show the proposed algorithm makes better acceleration.3)A GPU-CPU hybrid algorithm to improve the Power diagram algorithm based on L-BFGS optimization method is proposed.By optimizing the capacity and centroid calculation of the L-BFGS method,the GPU-CPU hybrid method can effectively accelerate the speed of the existing algorithms.By comparing with the original algorithm,it is proved that the improved algorithm has faster generation speed,higher precision and better adaptability.