摘要： 提出一种基于平面线段的反向最近邻查询方法，用于找出线段集中以查询线段作为最近邻的线段。通过构造线段集的Voronoi图处理不相交的线段。根据其邻接特性和局部特性，给出基于Voronoi图的线段反向最近邻查询算法及相关定理和证明。实验结果表明，反向最近邻方法易于找到相交的线段，具有较高的查询效率。

关键词: 平面线段, Voronoi图, 线段反向最近邻, 空间数据库, 查询区域

Abstract: Reverse Nearest Neighbor(RNN) query between line is put forward. That is finding the line segments that have query line segment as one of their nearest neighbors. According to whether two line segments are intersected, it has two categories: intersected line segment and no intersected. For the former, the reverse nearest neighbor is easy to find. For the latter, by constructing the Voronoi diagram of line segment sets, using the adjacent property and the local property, the line segment RNN query based on Voronoi diagram algorithm is proposed, and the relevant theorem and proof are given. Experimental results demonstrate the proposed algorithms have high query efficiency.

Key words: plane line segment, Voronoi graph, Line Reverse Nearest Neighbor(LRNN), spatial database, query region

中图分类号: 

• TP311