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

论文摘要

本文研究几个计算几何算法问题：颜色支撑点集的几何优化问题,移动网络Voronoi图的点定位问题,半平面Voronoi图的计算与性质问题,网络Frechet巨离和轨迹间基于Frechet距离检测频繁模式问题。本文的主要贡献如下：平面颜色支撑点集问题：平面上给定N个点M种颜色,如何为每种颜色选择一个点使得选出的M个点的一些几何属性极大或极小。本文证明颜色支撑点集的最大面积凸包,最大可能最近点对等问题是NP难的,并对最大面积凸包问题给出了2倍近似算法；本文接着证明最小生产树是NPO难的。对于颜色支撑点集的最大直径问题,本文给出了期望时间O(N log N)的算法。考虑移动网络Voronoi图问题：给定一个网络,假设有m个站点在网络的边上移动,本文设计算法计算站点移动时的动态网络Voronoi图来高效地回答最近邻居查询问题,接着推广到κ阶动态网络Voronoi图,以便能够高效回答前κ近站点查询。此外还考虑当查询点可以以一定速度移动时“最近”(最快时间赶到)站点查询问题。为了考察站点的方向,本文引入所谓的“半平面Voronoi图”它和正常的Voronoi图有很大的区别。本文研究了它的一些基本性质,并给出O(n log n)时间O(n)空间的算法计算n个方向一致点的半平面Voronoi图,对于任意方向点集的半平面Voronoi图,本文给出O(n2)时间O(n2log n)空间的算法来构造它。Frechet距离是衡量轨迹间相似性的重要标准,本文将欧几里得距离下的Frechet距离推广到网络距离,并给出了计算网络Frechet距离的算法。K.Buchin等研究了基于离散Frechet巨离,通过聚类子轨迹来检测频繁模式的问题,对于这个问题,在保持空间复杂度不变的情况下,本文给出了时间复杂度改进的算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究内容与研究现状
• 1.2.1 凸包、最小生成树、最大直径等问题的相关研究
• 1.2.2 Voronoi图的研究现状
• 1.2.3 基于Frechet距离的相关问题研究
• 1.3 本文的大致结构
• 第二章 基本概念、定义与术语
• 2.1 Voronoi图
• 2.2 网络Voronoi图
• 2.3 半平面Voronoi图
• 2.4 Frechet距离
• 2.5 Frechet自由空间和图表
• 2.6 离散Frechet距离
• 2.7 自由空间中的聚类曲线
• 第三章 颜色支撑点集的几何问题
• 3.1 引言
• 3.2 问题描述
• 3.3 计算颜色支撑点集最大直径
• 3.4 计算颜色支撑点集最大可能最近点对
• 3.5 计算颜色支撑点集最小生成树
• 3.6 计算颜色支撑点集最大面积凸包
• 3.7 本章小结
• 第四章 连续时间移动网络Voronoi图
• 4.1 引言
• 4.2 预处理工作
• 4.3 移动网络中的静态最近站点查询
• 4.4 移动网络中的静态K近站点查询
• 4.4.1 一个计算前K层下包络的平面扫描算法
• 4.4.2 一个计算前K层下包络的改进算法
• 4.5 移动网络中的动态最近站点查询
• 4.6 本章小结
• 第五章 Frechet距离的推广和应用
• 5.1 引言
• 5.2 网络Frechet距离定义
• 5.3 计算网络距离下的Frechet距离
• 5.3.1 判断问题
• 5.3.2 优化问题
• 5.4 SC（m,max,d）问题的改进算法
• 5.5 本章小结
• 第六章 半平面Voronoi图
• 6.1 平面Voronoi图的定义
• 6.2 半平面Voronoi复杂度的上限
• 6.3 计算方向一致点集的半平面Voronoi图
• 6.4 计算任意方向点集半平面Voronoi图
• 6.5 本章小结
• 第七章 总结与展望
• 参考文献
• 致谢
• 攻读硕士学位期间主要的研究成果