基于颜色支撑点集 voronoi图和fréchet距离的几何算法研究

《基于颜色支撑点集 voronoi图和fréchet距离的几何算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、mII

2、II

3、f1

4、I川

5、fIIIIlIIIfIII

6、Ⅲ《ⅢY1917808TheStUdyofGeometriCAIgorithmS：CoIor—SpanningSet，VoronoiDiagramandFr6chetDistanceSpeciaIty：￡Q堡p坠!曼!墨Qi曼塾曼曼垒卫亟墅鱼虹Q!QgYMasterDegreeCandidate：里垒垒￡h盟g!i塾SUperViSor：AssociatePro￡HeJianbiaoSchooIofInformationSCienCe＆EngineeringCentraISoUthUniVerSity

7、ChangShaHUnanP．R．C一----原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。储躲辫B凝：奠1年多具隐B关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文

8、的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所将本学位论文收录到《中国学位论文全文数据库》，并通过网络向社会公众提供信息服务。作者签名：龇师签名：竖也J孽B强t九

9、{年与具l书B摘要本文研究几个计算几何算法问题：颜色支撑点集的几何优化问题，移动网络Voronoi图的点定位问题，半平面V0ronoi图的计算与性质问题，网络F托chet距离和轨迹间基于Fr6chet距离检测频繁模式问题。本文的主要贡献如下：平面颜色支撑点集问题：平面上给定Ⅳ个点M种颜色，如何为每种颜色选择一个点使得选出的M个点的一些几何属性极大或极

10、小。本文证明颜色支撑点集的最大面积凸包，最大可能最近点对等问题是脚难的，并对最大面积凸包问题给出了2倍近似算法；本文接着证明最小生产树是Ⅳ尸D难的。对于颜色支撑点集的最大直径问题，本文给出了期望时间D(ⅣlogⅣ)的算法。考虑移动网络Voronoi图问题：给定一个网络，假设有所个站点在网络的边上移动，本文设计算法计算站点移动时的动态网络Voronoi图来高效地回答最近邻居查询问题，接着推广到七阶动态网络Voronoi图，以便能够高效回答前七近站点查询。此外还考虑当查询点可以以一定速度移动时“最近"(最快时间赶到)站点查询问题。为了考察站点的方向，本文引入

11、所谓的“半平面Voronoi图"，它和正常的Voronoi图有很大的区别。本文研究了它的一些基本性质，并给出D(刀log胛)时间D(刀)空间的算法计算刀个方向一致点的半平面Voronoi图，对于任意方向点集的半平面Voronoi图，本文给出D(甩2)时间D(n2log，1)空间的算法来构造它。Fr6chet距离是衡量轨迹间相似性的重要标准，本文将欧几里得距离下的Fr6chet距离推广到网络距离，并给出了计算网络Fr6chet距离的算法。K．Buchin等研究了基于离散Fr6chet距离，通过聚类子轨迹来检测频繁模式的问题m】，对于这个问题，在保持空间复杂

12、度不变的情况下，本文给出了时间复杂度改进的算法。关键词颜色支撑点集，移动网络Voronoi图，半平面Voronoi图，网络Fr6chet距离，聚类子轨迹AbstractInthisthesis，severalgeometricproblemsarestudied，includinggeometricproblenlSofcolor-sparulingsets，ponlocationinmoVingnetwork、7bronoidiagram，computationofhalfplaneV．oronoidiagram，ageneral娩ationofthe

13、Fr6chetdistanceiIlnetwork，2lrlddetectingcom删ningpattemofa仃ajecto巧bycluSteringsubtI．ajectories．Themaincontributionsofthisthesis羽．easf．ollows：Geome仃icproble螂ofcolor-spallllingsets：giVenⅣpoi吣withMc010rsiIltheplane，choosmgMpointswithdistinctcolors飘lChthatsomegeome旬ricpropertiesof朋’po

14、intsareIIlininlizedormxifllized．Weshowtl