Find in Library
Search millions of books, articles, and more
Indexed Open Access Databases
Efficient Algorithm for Constructing Order K Voronoi Diagrams in Road Networks
oleh: Bi Yu Chen, Huihuang Huang, Hui-Ping Chen, Wenxuan Liu, Xuan-Yan Chen, Tao Jia
Format: | Article |
---|---|
Diterbitkan: | MDPI AG 2023-04-01 |
Deskripsi
The order <i>k</i> Voronoi diagram (OkVD) is an effective geometric construction to partition the geographical space into a set of Voronoi regions such that all locations within a Voronoi region share the same k nearest points of interest (POIs). Despite the broad applications of OkVD in various geographical analysis, few efficient algorithms have been proposed to construct OkVD in real road networks. This study proposes a novel algorithm consisting of two stages. In the first stage, a new one-to-all <i>k</i> shortest path finding procedure is proposed to efficiently determine the shortest paths to <i>k</i> nearest POIs for each node. In the second stage, a new recursive procedure is introduced to effectively divide boundary links within different Voronoi regions using the hierarchical tessellation property of the OkVD. To demonstrate the applicability of the proposed OkVD construction algorithm, a case study of place-based accessibility evaluation is carried out. Computational experiments are also conducted on five real road networks with different sizes, and results show that the proposed OkVD algorithm performed significantly better than state-of-the-art algorithms.