关于k_1_k_n_阶Voronoi图生成算法的研究_顾晓青.pdf

第21 卷第7 期　　　 计算机应用与软件 Vol.21,No.7 2004 年7 月　　 Compu er Applica ions and Sof ware July 2004 关于k(1≤kn)阶Voronoi 图生成算法的研究 1, 2 1 1 1 顾晓青 　张有会 　赵　晔 　赵志辉 1 (河北师范大学数学与信息科学学院　石家庄 0500 16) 1 (河北工程技术高等专科学院基础部　沧州 06 100 1) 摘　要　　k(1≤kn)阶Voronoi 图由k 阶最近点Voronoi 图和 k 阶最远点Voronoi 图组成, 是 Voronoi 图的一种重要推广。 k 阶 Voronoi 图常用于确定平面点集中k 个点的最邻近或最远问题, 具有广泛的应用。 本文首先对k 阶Voronoi 图的基本性质进行了证 明, 并讨论了k 阶最近点与最远点Voronoi 图的关系, 最后, 给出了一种生成k 阶Voronoi 图的算法。 该算法思路清昕, 数据结构简洁, 易于实现, 并以图例验证了算法的有效性。 关键词　　计算几何　Voronoi 图　k 阶Voronoi 图 RESEARCH ON THE CONSTRUCTION ALGORITHM OF ORDER k(1≤kn)VORONOI DIAGRAM 1, 2 1 1 1 Gu Xiaoqing 　Zhang Yuohui 　Zhao Ye 　Zhao Zhihui 1 (College of Mathematics and Inf ormation Science, Hebei Normal University , Shij iazhuang 05001 ) 2 (Department of Basic Courses, Hebei Engineering and Technical College, Cangzhou 0 1001 ) Abstract　　Order k(1≤kn)voronoi diagram,w hich consis s of he k h-neares -poin voronoi diagram and k h-f ar hes-poin voronoi diagram, is an impor an generaliza ion of he ordiary voronoi diagram.I is of en used o solve he problem concerning k h neares or far hes poin s of a poin se and f inds i s applica ions in various fields.This paper firs gives a proof of he proper y of he k h-neares -poin voronoi diagram.And hen, i s udies he rela ion be ween he wo ypes of Order k voronoi diagram.In he end, w e develop an algori hm for forming Order k voronoi diagram s.The me hod w i h clear-c