Abstract: Voronoi diagram is an important branch of computational geometry and Voronoi diagrams based rough area are extensions of Voronoi diagrams. In this paper, a conception of Voronoi diagram based rough area is proposed and it is generated with the minimum distance between points of forming face and mother-points which is calculated out using A-star algorithm. For reducing the complexity of generating algorithm, a research on relation between weight of evaluation function of A-star algorithm and character of rough area is launched. Experimental results show that the optimal weight of evaluation function positively correlates with the roughness characteristics of rough area. Based on this, the optimal weight of A-star algorithm is obtained and the complexity of generating algorithm of Voronoi diagrams based rough area is remarkably reduced.

Key words: Voronoi diagram, rough area, A-star algorithm, evaluation function, optimal weight

摘要： Voronoi图是计算几何的一个重要分支，粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展。提出了粗糙域Voronoi图的概念并利用A*算法计算生成面上点与各母点的最短路径对其进行离散生成。为了降低粗糙域Voronoi图离散生成算法的复杂度，对粗糙域下A*算法估价函数权值与粗糙域粗糙特性的关系进行了深入探索。实验结果表明，A*算法估价函数权值与粗糙域粗糙特性正相关，并以此获得A*算法估价函数的最优权，大大降低了粗糙域Voronoi图离散生成算法的复杂度。

关键词: Voronoi图, 粗糙域, A*算法, 估价函数, 最优权