欢迎来到天天文库
浏览记录
ID:35104148
大小:4.95 MB
页数:72页
时间:2019-03-18
《高维voronoi图的生成与应用研究》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、^孝请;f^乂!Sou化ChinaUniversitofTe化noloygy工程硕±学位论文高维Vorono潤的生成与应用研究作者姓名王炫殊工程领域计算机技术-校内指导教师胡劲松教授校外指导教师邓健爽高级工程师所在学院计算机科学与工程学院论文提交日觀2016年3月TheGenerationandApplicationofHigher-DimensionalVoronoiDiagramADissertationSubmittedfortheDegreeofMasterCandidate:WangXuan
2、shuSupervisor:Prof.HuJinsongSouthChinaUniversityofTechnologyGuangzhou,China分类号:TP3学校代号;10561学号:2013210308621华南理工大学硕±学位论文高维Voronoi图的生成与应用研究■作者姓名:王炫殊指导教师姓名:、职称胡劲松教授申请学位级别:工程硕±工程领域名称:计算机技术/论文形式:□产品研发□工程设计曰应用研究□工程/项目管理□调研报告研究方向:计算几何及应用论文提交日期:日论文答辩日期年:75日却7月文!案月
3、(;%年3外I:华南理工大学学位授予日期学位授予单位:年月日答辩委员会成员:主席:嫂毕-?-委员:刮初化咎、弯句蘇巧、名表梅华南理工大学学位论文原创性声明t本人郑重声明:所呈交的论文是本人在导师的捲导下独立进行研究所。取得的研究成果除了文中特别加标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡。献的个人和集体,均已在文中明确方式标明本人完全意识到本声明的法律后果由本人承担。作者签名:至换詩\曰期:呵甚年^月2与曰学位论文版权使用授权书本学位论文作者完全了
4、解学校有关保留、使用学位论文的规定:,良P研究生在校攻读学位期间论文王作胸知识产权单位属华南理王大学。学校有权保存并向国家有关部口或机构送交论文的复印件和电子版,允许学位论文被查阅(除在保密期内的保密论文外);学校可W公布学位论文的全部或部分内容,可W允许采用影印、缩印或其它复制手段保存、汇编学位一论文。本人电子文档的内容和纸质论文的内容相致。本学□位论文属于:保密,在。□年解密后适用本授权书4^保密,同意在校园网上发布,供校内师生和与学校有共享协议全的文单位浏览;同意将本人学位论文提交中国学术期刊(光盘版)电子杂志社出版和
5、编入CNKI《中国知识资源总库》,传播学位论文的全部或部分内容。""(请在[^上相应方框内打V)'铅珠日期:wfrV叫作者签名:玉指导教师签名:日期:t作联者联系电话:电子邮箱:系地址(含邮编):摘要Voronoi图是计算几何(ComputationalGeometry)的一个重要的研究领域,在图形图像处理、计算机辅助设计(ComputerAidedDesign,CAD)、地理信息系统(GeographicInformationSystem,GIS)、空间邻域分析、路径规划、虚拟现实等等领域得到了广泛的应用。Voronoi生成算法
6、方面,学术界对于2维、3维空间的研究成果比较多。由于更高维的Voronoi图的拓扑结构、分析和实现都较为复杂,所以国内外对于任意维度上Voronoi图生成算法的研究并不是很多。本文针对这一研究领域的不足,利用了Voronoi图、Delaunay三角剖分和凸包三者之间的对应关系,研究和改进了高维凸包的生成算法,并应用于高维的Voronoi图的生成。本文首先对已有的、应为较为广泛的高维凸包算法进行了介绍和分析,并对它们的复杂度进行了研究。然后专注于Quickhull算法,ᨀ出了两方面的改进,并应用于生成高维Voronoi图。关于算法效率,本文ᨀ出了两点改进:一是对于数据
7、结构改进以ᨀ高搜索的效率,二是设计了算法并行执行的机制,将现有的算法改为并行执行。关于算法的健壮性也ᨀ出了两点改进:一是对于点集退化情形的处理,二是算法执行的过程中进行自检验,以保证算法当前执行的结果始终是正确的。第六章做了相应的实验来对比改进前后的算法,说明改进后的算法效率得到了明显的ᨀ高。在Voronoi图的应用方面,利用其各种优秀的性质,它被广泛应用在路径规划、高维聚类分析等等领域。此外学界也出现了一些跨领域应用的实例,比如与物理,化学、生物学、机械制造、移动通讯等领域相结合。随着高维Voronoi图应用需求的不断扩大,本文具有很好的理论和应用意义。关键词
此文档下载收益归作者所有