计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2004年
7期
18-19，73
,共3页
顾晓青%张有会%赵晔%赵志辉
顧曉青%張有會%趙曄%趙誌輝
고효청%장유회%조엽%조지휘
计算几何%Voronoi图%k阶Voronoi图
計算幾何%Voronoi圖%k階Voronoi圖
계산궤하%Voronoi도%k계Voronoi도
k(1≤k＜n)阶Voronoi图由k阶最近点Voronoi图和k阶最远点Voronoi图组成,是Voronoi图的一种重要推广.k阶Voronoi图常用于确定平面点集中k个点的最邻近或最远问题,具有广泛的应用.本文首先对k阶Voronoi图的基本性质进行了证明,并讨论了k阶最近点与最远点Voronoi图的关系,最后,给出了一种生成k阶Voronoi图的算法.该算法思路清昕,数据结构简洁,易于实现,并以图例验证了算法的有效性.
k(1≤k＜n)階Voronoi圖由k階最近點Voronoi圖和k階最遠點Voronoi圖組成,是Voronoi圖的一種重要推廣.k階Voronoi圖常用于確定平麵點集中k箇點的最鄰近或最遠問題,具有廣汎的應用.本文首先對k階Voronoi圖的基本性質進行瞭證明,併討論瞭k階最近點與最遠點Voronoi圖的關繫,最後,給齣瞭一種生成k階Voronoi圖的算法.該算法思路清昕,數據結構簡潔,易于實現,併以圖例驗證瞭算法的有效性.
k(1≤k＜n)계Voronoi도유k계최근점Voronoi도화k계최원점Voronoi도조성,시Voronoi도적일충중요추엄.k계Voronoi도상용우학정평면점집중k개점적최린근혹최원문제,구유엄범적응용.본문수선대k계Voronoi도적기본성질진행료증명,병토론료k계최근점여최원점Voronoi도적관계,최후,급출료일충생성k계Voronoi도적산법.해산법사로청흔,수거결구간길,역우실현,병이도례험증료산법적유효성.
