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

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

1、摘要本文研究几个计算几何算法问题：颜色支撑点集的几何优化问题，移动网络Voronoi图的点定位问题，半平面Voronoi图的计算与性质问题，网络F托chet距离和轨迹间基于Fr6chet距离检测频繁模式问题。本文的主要贡献如下：平面颜色支撑点集问题：平面上给定Ⅳ个点M种颜色，如何为每种颜色选择一个点使得选出的M个点的一些几何属性极大或极小。本文证明颜色支撑点集的最大面积凸包，最大可能最近点对等问题是ⅣP难的，并对最大面积凸包问题给出了2倍近似算法；本文接着证明最小生产树是Ⅳ尸D难的。对于颜色支撑点集的最大直径问题，本文给出了期望时间D(ⅣlogⅣ)的算法。

2、考虑移动网络Voronoi图问题：给定一个网络，假设有所个站点在网络的边上移动，本文设计算法计算站点移动时的动态网络Voronoi图来高效地回答最近邻居查询问题，接着推广到七阶动态网络Voronoi图，以便能够高效回答前七近站点查询。此外还考虑当查询点可以以一定速度移动时“最近"(最快时间赶到)站点查询问题。为了考察站点的方向，本文引入所谓的“半平面Voronoi图"，它和正常的Voronoi图有很大的区别。本文研究了它的一些基本性质，并给出D(刀log胛)时间D(刀)空间的算法计算刀个方向一致点的半平面Voronoi图，对于任意方向点集的半平面Voron

3、oi图，本文给出D(甩2)时间D(n2log，1)空间的算法来构造它。Fr6chet距离是衡量轨迹间相似性的重要标准，本文将欧几里得距离下的Fr6chet距离推广到网络距离，并给出了计算网络Fr6chet距离的算法。K．Buchin等研究了基于离散Fr6chet距离，通过聚类子轨迹来检测频繁模式的问题Ⅲ】，对于这个问题，在保持空间复杂度不变的情况下，本文给出了时间复杂度改进的算法。关键词颜色支撑点集，移动网络Voronoi图，半平面Voronoi图，网络Fr6chet距离，聚类子轨迹Abstract．．．●●●■．■’●’''’一Inthisthesis。

4、SeveralgeOmemcprOblemsarestudled，lrlcludlnggeometricproble傩ofcolor-spanningsets，pomlocationinmoVingnetwork、厂oronoidia伊am，computationofhalf巾lane、厂oronoidiagram，ageneral娩ationoftheFr6chetdistanceiIlnetwork，2lrlddetecting一一·●●‘●o■●啊’commutingpattemofa仃ajectorybyclusterlngsubtI．aJecto

5、rles．Jnernalncontributiollsofthisthesis羽．easf．ollows：Geome仃icproblemsofcolor-spanningsets：西VenⅣpointswithMcolorsiIltheplane，choosmgMpointswithdistinctcolorssuChthatson圮geometricprop酣iesofMpointsarernjni而zedorInaxi血zed．Weshowtllelargestclosestpair觚dlargestareaconVexhullareNP-ha咄and

6、百vc2-approxi瑚tionalgOrithmfor廿1elatterproblenFornlesmallestIIlininmmplanarspaIⅡling仃eeprobleIIl’weshowitisNPO—hard．Forthenmximumdiameterproble玛anD(ⅣlogⅣ)eXpectedtimealgorithmarepr0VidediIlthisthesis．Theproblemofmovingne铆orkVbronoidiagram：giVenane俩od('aIldsupposethereare朋sitesmovin

7、galongthene铆orkedges．Thealgorith麟tocomputetlledynarnjcne铆orkdiagramassitesmovesuCht11atonec锄a璐wer也encarestneighborque巧emcientlyarcprcsentedinthisthesis．Funhemorc，weeXtenditto七一orderdynaIIlicne铆orkVOronoidiagramsuchthatonecaIlanswermIe后nearestneighborqueqe伍ciently．Moreover'tlleprob

8、lemtoanswerⅡ1enearestsitequeWwhen