{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,1]],"date-time":"2026-09-01T07:49:58Z","timestamp":1788248998796,"version":"build-2803163510"},"reference-count":29,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2023,4,19]],"date-time":"2023-04-19T00:00:00Z","timestamp":1681862400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program","doi-asserted-by":"publisher","award":["2021YFB3900900"],"award-info":[{"award-number":["2021YFB3900900"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program","doi-asserted-by":"publisher","award":["2042022kf1199"],"award-info":[{"award-number":["2042022kf1199"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program","doi-asserted-by":"publisher","award":["42271473"],"award-info":[{"award-number":["42271473"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program","doi-asserted-by":"publisher","award":["2020CFA054"],"award-info":[{"award-number":["2020CFA054"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fundamental Research Funds for the Central Universities","award":["2021YFB3900900"],"award-info":[{"award-number":["2021YFB3900900"]}]},{"name":"Fundamental Research Funds for the Central Universities","award":["2042022kf1199"],"award-info":[{"award-number":["2042022kf1199"]}]},{"name":"Fundamental Research Funds for the Central Universities","award":["42271473"],"award-info":[{"award-number":["42271473"]}]},{"name":"Fundamental Research Funds for the Central Universities","award":["2020CFA054"],"award-info":[{"award-number":["2020CFA054"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["2021YFB3900900"],"award-info":[{"award-number":["2021YFB3900900"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["2042022kf1199"],"award-info":[{"award-number":["2042022kf1199"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["42271473"],"award-info":[{"award-number":["42271473"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["2020CFA054"],"award-info":[{"award-number":["2020CFA054"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003819","name":"Natural Science Foundation of Hubei Province","doi-asserted-by":"publisher","award":["2021YFB3900900"],"award-info":[{"award-number":["2021YFB3900900"]}],"id":[{"id":"10.13039\/501100003819","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003819","name":"Natural Science Foundation of Hubei Province","doi-asserted-by":"publisher","award":["2042022kf1199"],"award-info":[{"award-number":["2042022kf1199"]}],"id":[{"id":"10.13039\/501100003819","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003819","name":"Natural Science Foundation of Hubei Province","doi-asserted-by":"publisher","award":["42271473"],"award-info":[{"award-number":["42271473"]}],"id":[{"id":"10.13039\/501100003819","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003819","name":"Natural Science Foundation of Hubei Province","doi-asserted-by":"publisher","award":["2020CFA054"],"award-info":[{"award-number":["2020CFA054"]}],"id":[{"id":"10.13039\/501100003819","id-type":"DOI","asserted-by":"publisher"}]},{"name":"LIESMARS special Research Funding","award":["2021YFB3900900"],"award-info":[{"award-number":["2021YFB3900900"]}]},{"name":"LIESMARS special Research Funding","award":["2042022kf1199"],"award-info":[{"award-number":["2042022kf1199"]}]},{"name":"LIESMARS special Research Funding","award":["42271473"],"award-info":[{"award-number":["42271473"]}]},{"name":"LIESMARS special Research Funding","award":["2020CFA054"],"award-info":[{"award-number":["2020CFA054"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>The order k 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 k shortest path finding procedure is proposed to efficiently determine the shortest paths to k 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.<\/jats:p>","DOI":"10.3390\/ijgi12040172","type":"journal-article","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T01:42:39Z","timestamp":1681954959000},"page":"172","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Algorithm for Constructing Order K Voronoi Diagrams in Road Networks"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3591-9968","authenticated-orcid":false,"given":"Bi Yu","family":"Chen","sequence":"first","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China"},{"name":"Collaborative Innovation Center of Geospatial Technology, Wuhan University, Wuhan 430079, China"},{"name":"Hubei Luojia Laboratory, Wuhan 430079, China"},{"name":"Geocomputation Center for Social Sciences, Wuhan University, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huihuang","family":"Huang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hui-Ping","family":"Chen","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China"},{"name":"Hubei Luojia Laboratory, Wuhan 430079, China"},{"name":"School of Management, Huazhong University of Science and Technology, Wuhan 430074, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenxuan","family":"Liu","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuan-Yan","family":"Chen","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Jia","sequence":"additional","affiliation":[{"name":"Geocomputation Center for Social Sciences, Wuhan University, Wuhan 430079, China"},{"name":"School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,4,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1080\/13658810701587891","article-title":"Generalized network Voronoi diagrams: Concepts, computational methods, and applications","volume":"22","author":"Okabe","year":"2008","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.compenvurbsys.2015.02.001","article-title":"Generation of constrained network Voronoi diagram using linear tessellation and expansion method","volume":"51","author":"Ai","year":"2015","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/10095020.2016.1146440","article-title":"Tessellations in GIS: Part I\u2014Putting it all together","volume":"19","author":"Gold","year":"2016","journal-title":"Geo-Spat. Inf. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/j.compenvurbsys.2015.03.005","article-title":"Weighted network Voronoi Diagrams for local spatial analysis","volume":"52","author":"She","year":"2015","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.isprsjprs.2004.04.001","article-title":"Voronoi-based k-order neighbour relations for spatial analysis","volume":"59","author":"Chen","year":"2004","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_6","first-page":"1115","article-title":"Understanding the Impacts of Human Mobility on Accessibility Using Massive Mobile Phone Tracking Data","volume":"108","author":"Chen","year":"2018","journal-title":"Ann. Am. Assoc. Geogr."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"6519","DOI":"10.1080\/10106049.2021.1943008","article-title":"Analysis of the spatial range of service and accessibility of hospitals designated for coronavirus disease 2019 in Yunnan Province, China","volume":"37","author":"Zheng","year":"2021","journal-title":"Geocarto Int."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1080\/13658816.2021.1976409","article-title":"An exact statistical method for analyzing co-location on a street network and its computational implementation","volume":"36","author":"Morioka","year":"2021","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.tre.2013.11.003","article-title":"A bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem","volume":"61","author":"Tu","year":"2014","journal-title":"Transp. Res. Part E: Logist. Transp. Rev."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Shamos, M.I., and Hoey, D. (1975, January 13\u201315). Closest-point problems. Proceedings of the 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), Washington, DC, USA.","DOI":"10.1109\/SFCS.1975.8"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF01228508","article-title":"A semidynamic construction of higher-order voronoi diagrams and its randomized analysis","volume":"9","author":"Boissonnat","year":"1993","journal-title":"Algorithmica"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1080\/13658816.2011.609488","article-title":"An improved distance metric for the interpolation of link-based traffic data using kriging: A case study of a large-scale urban road network","volume":"26","author":"Zou","year":"2012","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1080\/13658816.2016.1238919","article-title":"Measuring place-based accessibility under travel time uncertainty","volume":"31","author":"Chen","year":"2016","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.14778\/1453856.1453973","article-title":"The V*-Diagram","volume":"1","author":"Nutanong","year":"2008","journal-title":"Proc. VLDB Endow."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Chen, Z., Han, J., Wang, B., and Liu, W. (2010, January 3\u20135). Voronoi-based k-path nearest neighbor query in road networks. Proceedings of the 2010 International Conference on Computer and Information Application, Tianjin, China.","DOI":"10.1109\/ICCIA.2010.6141535"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Ohsawa, Y., Htoo, H., Nyunt, N.J., and Sein, M.M. (2015, January 8\u201311). Generalized bichromatic homogeneous vicinity query algorithm in road network distance. Proceedings of the New Trends in Databases and Information Systems: ADBIS 2015 Short Papers and Workshops, BigDap, DCSA, GID, MEBIS, OAIS, SW4CH, WISARD, Poitiers, France.","DOI":"10.1007\/978-3-319-23201-0_8"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1080\/13658816.2013.816427","article-title":"Map-matching algorithm for large-scale low-frequency floating car data","volume":"28","author":"Chen","year":"2013","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1002\/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L","article-title":"The graph Voronoi diagram with applications","volume":"36","author":"Erwig","year":"2000","journal-title":"Networks"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1111\/tgis.12133","article-title":"A Hybrid Link-Node Approach for Finding Shortest Paths in Road Networks with Turn Restrictions","volume":"19","author":"Li","year":"2015","journal-title":"Trans. GIS"},{"key":"ref_20","unstructured":"Ohsawa, Y., Htoo, H., and Sein, M.M. (2016). East European Conference on Advances in Databases and Information Systems, Springer. MERAL Portal."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"101849","DOI":"10.1016\/j.compenvurbsys.2022.101849","article-title":"Transit Voronoi diagrams in multi-mode public transport networks","volume":"96","author":"Chen","year":"2022","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1080\/13658816.2015.1104317","article-title":"Spatiotemporal data model for network time geographic analysis in the era of big data","volume":"30","author":"Chen","year":"2016","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Shi, C., Chen, B., and Li, Q. (2017). Estimation of Travel Time Distributions in Urban Road Networks Using Low-Frequency Floating Car Data. ISPRS Int. J. Geo-Inf., 6.","DOI":"10.3390\/ijgi6080253"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.jtrangeo.2003.10.005","article-title":"Accessibility evaluation of land-use and transport strategies: Review and research directions","volume":"12","author":"Geurs","year":"2004","journal-title":"J. Transp. Geogr."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2220","DOI":"10.1017\/S1368980014002742","article-title":"Healthy food access for urban food desert residents: Examination of the food environment, food purchasing practices, diet and BMI","volume":"18","author":"Dubowitz","year":"2014","journal-title":"Public Health Nutr."},{"key":"ref_28","unstructured":"Chen, B.Y., Fu, C.-X., and Huang, H.-H. Measuring food accessibility using K nearest neighbor distance, Working paper."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"12877","DOI":"10.1109\/TITS.2021.3118206","article-title":"Vehicle Re-identification for Lane-level Travel Time Estimations on Congested Urban Road Networks Using Video Images","volume":"23","author":"Zhang","year":"2022","journal-title":"IEEE Trans. Intell. Transp. Syst."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/12\/4\/172\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:19:13Z","timestamp":1760123953000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/12\/4\/172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,19]]},"references-count":29,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,4]]}},"alternative-id":["ijgi12040172"],"URL":"https:\/\/doi.org\/10.3390\/ijgi12040172","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,19]]}}}