Abstract: The reverse k nearest region query is a new problem. In order to make up for the existing research results which can not effectively deal with the line reverse k nearest region query problem in the obstacle space, this paper proposes the reverse k nearest region query of line segment method based on Voronoi graph in obstacle environment. In practice, it is mainly used to evaluate the influence of query objects. Firstly, the method reduces the data   region set and reduces the search range of the query. Then, based on the theorem of the pruning process, it filters the candidate set to obtain more accurate candidate selections. Finally, according to the nature of the Voronoi graph, some related theorems are proposed to refine the result set of OLRkNN (obstacle line reverse k nearest neighbor) query. This method greatly changes the query speed and query accuracy in the process of pruning and refining       according to the characteristics of the Voronoi graph. Theoretical studies and experiments show that the proposed method can effectively deal with the problem of the reverse k nearest region query based on line segment in obstacle environment.

Key words: obstacle space, Voronoi graph, line segment, reverse k nearest region

摘要： 反k最近区域查询问题是近邻查询领域的一个新问题，为了弥补现有的研究成果无法有效地处理障碍空间下的线段反k最近区域查询问题，提出了在障碍环境下基于Voronoi图的线段反k最近区域查询方法。在实际中主要应用于评估查询对象的影响力。该方法首先对数据区域集进行约减，缩减了查询的搜索范围。然后根据剪枝过程所提定理对候选集进行过滤，获得更精确的候选集。最后基于Voronoi图的性质提出相关定理，精炼OLRkNR（obstacle line reverse k nearest region）查询的结果集。所提方法根据Voronoi图特性在剪枝、精炼过程中提升了查询速度和查询准确率。理论研究和实验表明，所提方法可以有效处理障碍环境下基于线段的反[k]最近区域查询问题。

关键词: 障碍空间, Voronoi图, 线段, 反k最近区域