A Method for k Nearest Neighbor Query of Line Segment in Obstructed Spaces

• Published in: Journal of information processing systems 2020, 16(2), 62, pp.406-420
• Main Authors: Liping Zhang, Song Li, Yingying Guo, Xiaohong Hao
• Format: Article
• Language: English
• Subjects: 컴퓨터학
• ISSN: 1976-913X; 2092-805X
• DOI: 10.3745/JIPS.04.0167

In order to make up the deficiencies of the existing research results which cannot effectively deal with thenearest neighbor query based on the line segments in obstacle space, the k nearest neighbor query method ofline segment in obstacle space is proposed and the STA_OLkNN algorithm under the circumstance of staticobstacle data set is put forward. The query process is divided into two stages, including the filtering processand 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 expressionmethod is put forward and the final result is obtained by comparing the distance. Theoretical research andexperimental results show that the proposed algorithm can effectively deal with the problem of k nearestneighbor query of the line segment in the obstacle environment. KCI Citation Count: 0