A hierarchical proximity search algorithm based on Voronoi diagram

作者：Cai Qiang; Cheng Baiyu^*; Li Haisheng; Mao Dianhui

来源：Journal of Information and Computational Science, 2014, 11(14): 4931-4941.

DOI：10.12733/jics20104485

• Adjacent relation
• Density of road network
• Dijkstra algorithms
• Neighboring properties
• Search Algorithms
• Search efficiency
• Space division
• Voronoi diagrams

In the paper, space partition can filter out a lot of useless information in the search process, so it can increase the search efficiency. According to the problems that the large-scale road network partition more layers, pretreatment time consumption and storage space has more, current search methods are difficult to be directly applied to the large-scale road network. To solve this problem, a hierarchical proximity search algorithm based on Voronoi diagram is proposed. Using the Voronoi diagram immediately adjacent properties and the space division, first, the space of road network is divided in accordance with the density of road network, and then solving the adjacency relationship between the respective regions, the search is limited in scope with the target object with the adjacent relation. At last, using Dijkstra algorithm solves the optimal path between the starting point and the ending point in these connected regions. Examples to verify the efficiency of the proposed method.

• 出版日期2014