关键词: 加权Voronoi图, 四叉树结构, 相关生长源区域, 时间消耗值

Abstract: Considering the limitation of research on ordinary Voronoi diagram and low efficiency of the capabilities to build weighted voronoi diagram, a method based on quadtree structure for generating weighted Voronoi diagram was proposed in this paper. The key idea of this method was to obtain searched correlated seeds region of the nonexpansion nodes by the quadtree structure, calculate the time consumption value to replace weighted distance, and determine the ownership seed according to the node shortest time consumption value. The computing model based on quadtree structure and several basic characteristics of the method were given. The test result shows that the seeds are rapidly dilated, the time complexity gets effectively lower than uniform grid structure. The algorithm is simple, and it has a strong maneuverability and practical value.

Key words: weighted Voronoi diagram, quadtree structure, related seed region, times consumption value