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

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