探索关于高阶voronoi图快速生成算法的研究

《探索关于高阶voronoi图快速生成算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、河北师范大学硕士学位论文关于高阶Voronoi图快速生成算法的研究姓名：刘红娟申请学位级别：硕士专业：计算机应用技术指导教师：张有会20080308摘要高阶Voronoi图是普通Voronoi图的一种重要推广，在解决平面点集多个点的邻近问题中有着广泛的应用。然而，以往的高阶Voronoi图生成算法构造代价较高，时间复杂度较大，因而限制了高阶Voronoi图在实际应用中的推广。本文介绍了k(14k

2、ronoi图生成算法的基础上，依据“限定上界(FixedUpperBound)”定理，提出了一种基于屏幕自适应分区实现局部查找k个邻近点的快速生成七阶Voronoi图以及k阶有顺序Voronoi图的算法。除此之外，该算法还能用于生成多种不同形式的高阶Voronoi图。这种生成k阶Voronoi图的算法思路清晰，数据结构简洁，在保证图形效果的前提下，生成速度得到了显著提高。该算法已在Visualc++环境下实现，从而验证了算法的有效性。关键字；计算几何Voronoi图高阶Voronoi图自适应IIIAbstractHigher-orderVoronoidiagramisallimportant

3、generalizationofordinaryVoronoidiagram．Ithaswidespreadapplicationsintheproblemoffindingk-nearestneighborsinaplanarpo硫set．However,thepreviousalgorithmsofconstructinghigher-orderVoronoidiagramhavecomplexdatastructureandhightimecomplexity．Duetothesefeatureshigher-orderVoronoidiagramislimitedinpractica

4、luse．Thisarticleintroducesthedefinitionandpropertiesofk-nearest(1≤k

5、anconstructmanykindsofdifferenthigher-orderVoronoidiagram，butalsohasclearideas，simpledatastructureanditscomputationalspeedisnotablyincreased，onthepremiseofhighdiagramquality．Finally,ThisalgorithmhasbeenachievedinVisualC++，SOthevalidityofthisalgorithmiseasilyveri6ed．KeyWords：computationalgeometryVor

6、onoidiagramhigherorderVoronoidiagramAdaptiveIV学位论文原创性声明本人所提交的学位论文《关于高阶Voronoi图快速生成算法的研究》，是在导师的指导下，独立进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中标明。本声明的法律后果由本人承担。论文作者(签名)：剖；五埔a口p孑年r月心日指导教师确认(签名)：豕较丽参么巾汐年，月∞日学位论文版权使用授权书本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和

7、磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。(保密的学位论文在——年解密后适用本授权书)论文作者(签名)：纠轻确上嘞年r月f牛日‘指导教师(签名)：丕坎丽夸70-o莎年，月加日11绪论Voronoi图n1是计算几何的一个重要分支，在计算几何的理论研究和应用研究中起着重要的作用。平面上由n个点生成的Vo