Liping Zhang, Song Li, Yingying Guo, Xiaohong Hao, Journal of Information Processing Systems Vol. 16, No. 2, pp. 406-420, Apr. 2020  

https://doi.org/10.3745/JIPS.04.0167
Keywords: Line Segment k Nearest Neighbor, Line Segment Obstacle Distance, Line Segment Voronoi Diagram, Nearest Neighbor Query, spatial database
Fulltext: PDF Full Text PubReader

Abstract

"In order to make up the deficiencies of the existing research results which cannot effectively deal with the nearest neighbor query based on the line segments in obstacle space, the k nearest neighbor query method of line segment in obstacle space is proposed and the STA_OLkNN algorithm under the circumstance of static obstacle data set is put forward. The query process is divided into two stages, including the filtering process and refining process. In the filtration process, according to the properties of the line segment Voronoi diagram, the corresponding pruning rules are proposed and the filtering algorithm is presented. In the refining process, according to the relationship of the position between the line segments, the corresponding distance expression method is put forward and the final result is obtained by comparing the distance. Theoretical research and experimental results show that the proposed algorithm can effectively deal with the problem of k nearest neighbor query of the line segment in the obstacle environment."

Statistics
Cite this article