{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:15:51Z","timestamp":1760231751141,"version":"build-2065373602"},"reference-count":45,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2022,5,12]],"date-time":"2022-05-12T00:00:00Z","timestamp":1652313600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"JSPS KAKENHI","award":["JP21H05847","JP21K17701"],"award-info":[{"award-number":["JP21H05847","JP21K17701"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Although graph theory has already been introduced in spatial reasoning, current spatial database systems do not provide out-of-the-box routing on geometric points that are not matched on the graph. Methods that connect new reference locations to the graph render different routing results. Moreover, current solutions break reasoning down to local analysis. We bridge the gap between routing networks and spatial geometry by a global matching of geometric points to routing networks.<\/jats:p>","DOI":"10.3390\/a15050163","type":"journal-article","created":{"date-parts":[[2022,5,12]],"date-time":"2022-05-12T05:10:32Z","timestamp":1652332232000},"page":"163","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Linking Off-Road Points to Routing Networks"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8721-4444","authenticated-orcid":false,"given":"Dominik","family":"K\u00f6ppl","sequence":"first","affiliation":[{"name":"M&D Data Science Center, Tokyo Medical and Dental University, Tokyo 113-8510, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2022,5,12]]},"reference":[{"key":"ref_1","unstructured":"Barry Devlin, S.R., and Myers, J. (2012). Big Data Comes of Age, 9sight. EMA and 9sight Consulting Report."},{"key":"ref_2","unstructured":"National Imagery and Mapping Agency (2000). Department of Defense World Geodetic System 1984: Its Definition and Relationships with Local Geodetic Systems, Technical Report TR8350.2."},{"key":"ref_3","unstructured":"Snyder, J. (1997). Flattening the Earth: Two Thousand Years of Map Projections, University of Chicago Press."},{"key":"ref_4","unstructured":"Herring, J.R. (2010). OpenGIS Implementation Standard for Geographic Information\u2014Simple Feature Access\u2014Part 2: SQL Option, OGC. Technical Report."},{"key":"ref_5","unstructured":"Monmonier, M. (2010). Rhumb Lines and Map Wars: A Social History of the Mercator Projection, University of Chicago Press."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Moon, P., and Spencer, D.E. (1961). Field Theory Handbook, Including Coordinate Systems, Differential Equations and Their Solutions, Springer. [1st ed.].","DOI":"10.1007\/978-3-642-83243-7_6"},{"key":"ref_7","unstructured":"Abbena, E., Salamon, S., and Gray, A. (2006). Modern Differential Geometry of Curves and Surfaces with Mathematica, Taylor & Francis. [3rd ed.]. Textbooks in Mathematics."},{"key":"ref_8","first-page":"979","article-title":"Automatic Completion And Evaluation of Road Networks","volume":"33","author":"Wiedemann","year":"2000","journal-title":"Int. Arch. Photogramm. Remote Sens."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/978-3-642-40235-7_14","article-title":"Compact Representation of GPS Trajectories over Vectorial Road Networks","volume":"Volume 8098","author":"Nascimento","year":"2013","journal-title":"Advances in Spatial and Temporal Databases"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Haunert, J.H., and Budig, B. (2012, January 6\u20139). An Algorithm for Map Matching Given Incomplete Road Data. Proceedings of the 20th International Conference on Advances in Geographic Information Systems, SIGSPATIAL \u201912, Redondo Beach, CA, USA.","DOI":"10.1145\/2424321.2424402"},{"key":"ref_11","unstructured":"Wolfson, O., Agrawal, D., and Lu, C.T. (2009, January 4\u20136). Map-matching for low-sampling-rate GPS trajectories. Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, WA, USA."},{"key":"ref_12","unstructured":"Dahlgren, A., and Harrie, L. (2007, January 8\u201311). Development of a tool for proximity applications. Proceedings of the 10th AGILE International Conference on Geographic Information, Aalborg, Denmark."},{"key":"ref_13","unstructured":"de Jong, T., and Tillema, T. (2005). Transport network extensions for accessibility analysis in geographic information systems. Afr. GIS, 627, Available online: https:\/\/dspace.library.uu.nl\/handle\/1874\/11335."},{"key":"ref_14","first-page":"3","article-title":"Connect the dot: Computing feed-links for network extension","volume":"3","author":"Aronov","year":"2011","journal-title":"JOSIS"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.comgeo.2014.09.006","article-title":"Linear Time Algorithm for Optimal Feed-link Placement","volume":"48","author":"Savic","year":"2015","journal-title":"Comput. Geom."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1109\/TMC.2005.16","article-title":"A Location-Based Routing Method for Mobile Ad Hoc Networks","volume":"4","author":"Blazevic","year":"2005","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Durocher, S., Gasieniec, L., and Wong, P.W.H. (2016). Routing in Geometric Networks. Encyclopedia of Algorithms, Springer.","DOI":"10.1007\/978-1-4939-2864-4_352"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., and Murty, U.S.R. (1976). Graph Theory with Applications, Elsevier.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"K\u00f6ppl, D. (2022). Inferring Spatial Distance Rankings with Partial Knowledge on Routing Networks. Information, 13.","DOI":"10.3390\/info13040168"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"K\u00fchnel, W. (2005). Differentialgeometrie, Vieweg Studium.","DOI":"10.1007\/978-3-322-93422-2"},{"key":"ref_21","unstructured":"do Carmo, M. (1976). Differential Geometry of Curves and Surfaces, Pearson Education Canada."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s00190-002-0253-x","article-title":"Two different methods of geoidal height determinations using a spherical harmonic representation of the geopotential, topographic corrections and the height anomaly\u2014Geoidal height difference","volume":"76","author":"Nahavandchi","year":"2002","journal-title":"J. Geod."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s00190-012-0578-z","article-title":"Algorithms for geodesics","volume":"87","author":"Karney","year":"2013","journal-title":"J. Geod."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1179\/sre.1975.23.176.88","article-title":"Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations","volume":"22","author":"Vincenty","year":"1975","journal-title":"Surv. Rev."},{"key":"ref_25","first-page":"81","article-title":"Geodesics on an oblate spheroid","volume":"25","author":"Forsyth","year":"1896","journal-title":"Messenger Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/971697.602266","article-title":"R-trees: A Dynamic Index Structure for Spatial Searching","volume":"14","author":"Guttman","year":"1984","journal-title":"SIGMOD Rec."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Roussopoulos, N., Kelley, S., and Vincent, F. (1995, January 22\u201325). Nearest Neighbor Queries. Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201995, San Jose, CA, USA.","DOI":"10.1145\/223784.223794"},{"key":"ref_28","first-page":"17","article-title":"OpenGIS: Tales from a Small Market Town","volume":"Volume 1580","author":"Vckovski","year":"1999","journal-title":"International Conference on Interoperating Geographic Information Systems"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Shekhar, S., and Xiong, H. (2008). PostGIS. Encyclopedia of GIS, Springer.","DOI":"10.1007\/978-0-387-35973-1"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Wenzel, F., K\u00f6ppl, D., and Kie\u00dfling, W. (2013). Interactive Toolbox for Spatial-Textual Preference Queries. International Symposium on Spatial and Temporal Databases, Springer.","DOI":"10.1007\/978-3-642-40235-7_29"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Zhang, L., and He, X. (2012). Route Search Base on pgRouting. Software Engineering and Knowledge Engineering: Theory and Practice, Springer.","DOI":"10.1007\/978-3-642-25349-2_133"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Prandi, F., De Amicis, R., Conti, G., and Debiasi, A. (2012, January 4\u20135). Use of OGC Web Standard for a Spatio-temporal Enabled SDI for Civil Protection. Proceedings of the 17th International Conference on 3D Web Technology, Web3D \u201912, Los Angeles, CA, USA.","DOI":"10.1145\/2338714.2338732"},{"key":"ref_33","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_34","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_35","first-page":"24","article-title":"Hierarchical Hub Labelings for Shortest Paths","volume":"Volume 7501","author":"Epstein","year":"2012","journal-title":"European Symposium on Algorithms"},{"key":"ref_36","first-page":"319","article-title":"Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks","volume":"Volume 5038","author":"Geisberger","year":"2008","journal-title":"International Workshop on Experimental and Efficient Algorithms"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2886843","article-title":"Customizable Contraction Hierarchies","volume":"21","author":"Dibbelt","year":"2016","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Gottesb\u00fcren, L., Hamann, M., Uhl, T.N., and Wagner, D. (2019). Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies. Algorithms, 12.","DOI":"10.3390\/a12090196"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Strasser, B., Wagner, D., and Zeitz, T. (2021). Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks. Algorithms, 14.","DOI":"10.3390\/a14030090"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/978-3-030-58150-3_10","article-title":"Seamless Interpolation Between Contraction Hierarchies and Hub Labels for Fast and Space-Efficient Shortest Path Queries in Road Networks","volume":"Volume 12273","author":"Kim","year":"2020","journal-title":"International Computing and Combinatorics Conference"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Rupp, T., and Funke, S. (2021). A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels and a Provably Optimal Instance-Based Schema. Algorithms, 14.","DOI":"10.3390\/a14060164"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Zhang, M., Li, L., Hua, W., Mao, R., Chao, P., and Zhou, X. (2021, January 19\u201322). Dynamic Hub Labeling for Road Networks. Proceedings of the 2021 IEEE 37th International Conference on Data Engineering (ICDE), Chania, Greece.","DOI":"10.1109\/ICDE51399.2021.00036"},{"key":"ref_43","unstructured":"Theurer, D. (2013). Incremental Updates of Contraction Hierarchies for Road Network Routing. [Master\u2019s Thesis, University of Dublin]."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"2215","DOI":"10.1137\/S0097539795289604","article-title":"An Optimal Algorithm for Euclidean Shortest Paths in the Plane","volume":"28","author":"Hershberger","year":"1999","journal-title":"SIAM J. Comput."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/978-3-540-87473-7_19","article-title":"Road Networks and Their Incomplete Representation by Network Data Models","volume":"Volume 5266","author":"Cova","year":"2008","journal-title":"Geographic Information Science"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/5\/163\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:09:41Z","timestamp":1760137781000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/5\/163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,12]]},"references-count":45,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,5]]}},"alternative-id":["a15050163"],"URL":"https:\/\/doi.org\/10.3390\/a15050163","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,5,12]]}}}