最大空圆约束下的最邻近计算方法

Nearest neighbor searching algorithm with largest empty circle constraint

移动目标的最邻近查询是位置服务的重要内容之一。本文针对地理目标分布不均的情况,将离散点集的最大空圆参数引入到最邻近查询中,提出了最大空圆约束下的k-D树最邻近查询算法。通过实验证明该算法可以有效地减少节点访问次数,减少距离计算次数,从而提高最邻近的查询效率。进而将该算法应用于移动目标的k阶邻近查询中,可以有效地减少移动点在三角网中的定位次数,改善k阶邻近的查询效率。

The nearest neighbor queries of moving objects are of important service terms in LBS （Location-Based Services ） field. But the uneven distribution of geographical objects greatly deteriorates the searching efficiency. This paper proposed an optimization nearest neighbor searching algorithm based on k-D tree with the largest empty circle constraint of discrete point set. The experiment showed the new algorithm could be better comparing with non-constraint algorithm in searching efficiency, because it effectively reduced the number of visiting nodes also the number of calculating distance. Furthermore, this algorithm could be used in searching korder neighbor objects of moving objects to reduce the positioning number in the triangle network.