基于Voronoi图的连续反向最近邻查询

为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。

Continuous Reverse Nearest Neighbor Search Based on Voronoi Diagram

In order to solve continuous reverse nearest neighbor query of moving points in dynamic environment, continuous reverse nearest neighbor query is divided into monochromatic and bichromatic study. By using Voronoi diagram of moving points, monochromatic continuous reverse nearest neighbor and bichromatic continuous reverse nearest neighbor query algorithm are given. The relevant theorem and proof of the algorithm＇s correctness and termination are given, and its time complexity analysis is presented. According to whether the topology of the Voronoi diagram of moving points changes, it has two categories： change and no change. By analysis of candidate region changes in each category, Voronoi diagram is reconstructed in change region, and corresponding solutions are given. In most cases, the query results can be found only needing generate Voronoi diagram of local moving points. It can reduce the cost of continuous reverse nearest neighbor queries.