高维voronoi图的生成与应用研究

《高维voronoi图的生成与应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、＾孝请；ｆ＾乂！Ｓｏｕ化ＣｈｉｎａＵｎｉｖｅｒｓｉｔｏｆＴｅ化ｎｏｌｏｙｇｙ工程硕±学位论文高维Ｖｏｒｏｎｏ潤的生成与应用研究作者姓名王炫殊工程领域计算机技术－校内指导教师胡劲松教授校外指导教师邓健爽高级工程师所在学院计算机科学与工程学院论文提交日觀２０１６年３月TheGenerationandApplicationofHigher-DimensionalVoronoiDiagramADissertationSubmittedfortheDegreeofMasterCandidate：WangXuan

2、shuSupervisor：Prof.HuJinsongSouthChinaUniversityofTechnologyGuangzhou,China分类号：ＴＰ３学校代号；１０５６１学号：２０１３２１０３０８６２１华南理工大学硕±学位论文高维Ｖｏｒｏｎｏｉ图的生成与应用研究■作者姓名：王炫殊指导教师姓名：、职称胡劲松教授申请学位级别：工程硕±工程领域名称：计算机技术／论文形式：□产品研发□工程设计曰应用研究□工程／项目管理□调研报告研究方向：计算几何及应用论文提交日期：日论文答辩日期年：７５日却７月文！案月

3、（；％年３外Ｉ：华南理工大学学位授予日期学位授予单位：年月日答辩委员会成员：主席：嫂毕－？－委员：刮初化咎、弯句蘇巧、名表梅华南理工大学学位论文原创性声明ｔ本人郑重声明：所呈交的论文是本人在导师的捲导下独立进行研究所。取得的研究成果除了文中特别加标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡。献的个人和集体，均已在文中明确方式标明本人完全意识到本声明的法律后果由本人承担。作者签名：至换詩＼曰期：呵甚年＾月２与曰学位论文版权使用授权书本学位论文作者完全了

4、解学校有关保留、使用学位论文的规定：，良Ｐ研究生在校攻读学位期间论文王作胸知识产权单位属华南理王大学。学校有权保存并向国家有关部口或机构送交论文的复印件和电子版，允许学位论文被查阅（除在保密期内的保密论文外）；学校可Ｗ公布学位论文的全部或部分内容，可Ｗ允许采用影印、缩印或其它复制手段保存、汇编学位一论文。本人电子文档的内容和纸质论文的内容相致。本学□位论文属于：保密，在。□年解密后适用本授权书４＾保密，同意在校园网上发布，供校内师生和与学校有共享协议全的文单位浏览；同意将本人学位论文提交中国学术期刊（光盘版）电子杂志社出版和

5、编入ＣＮＫＩ《中国知识资源总库》，传播学位论文的全部或部分内容。＂＂（请在［＾上相应方框内打Ｖ）＇铅珠日期：ｗｆｒＶ叫作者签名：玉指导教师签名：日期：ｔ作联者联系电话：电子邮箱：系地址（含邮编）：摘要Voronoi图是计算几何（ComputationalGeometry）的一个重要的研究领域，在图形图像处理、计算机辅助设计（ComputerAidedDesign,CAD）、地理信息系统（GeographicInformationSystem，GIS）、空间邻域分析、路径规划、虚拟现实等等领域得到了广泛的应用。Voronoi生成算法

6、方面，学术界对于2维、3维空间的研究成果比较多。由于更高维的Voronoi图的拓扑结构、分析和实现都较为复杂，所以国内外对于任意维度上Voronoi图生成算法的研究并不是很多。本文针对这一研究领域的不足，利用了Voronoi图、Delaunay三角剖分和凸包三者之间的对应关系，研究和改进了高维凸包的生成算法，并应用于高维的Voronoi图的生成。本文首先对已有的、应为较为广泛的高维凸包算法进行了介绍和分析，并对它们的复杂度进行了研究。然后专注于Quickhull算法，ᨀ出了两方面的改进，并应用于生成高维Voronoi图。关于算法效率，本文ᨀ出了两点改进：一是对于数据

7、结构改进以ᨀ高搜索的效率，二是设计了算法并行执行的机制，将现有的算法改为并行执行。关于算法的健壮性也ᨀ出了两点改进：一是对于点集退化情形的处理，二是算法执行的过程中进行自检验，以保证算法当前执行的结果始终是正确的。第六章做了相应的实验来对比改进前后的算法，说明改进后的算法效率得到了明显的ᨀ高。在Voronoi图的应用方面，利用其各种优秀的性质，它被广泛应用在路径规划、高维聚类分析等等领域。此外学界也出现了一些跨领域应用的实例，比如与物理，化学、生物学、机械制造、移动通讯等领域相结合。随着高维Voronoi图应用需求的不断扩大，本文具有很好的理论和应用意义。关键词