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

摘要

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