{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T17:47:16Z","timestamp":1759513636804,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            Given an arbitrary real constant \u03b5 &gt; 0, and a geometric graph\n            <jats:italic>G<\/jats:italic>\n            in\n            <jats:italic>d<\/jats:italic>\n            -dimensional Euclidean space with\n            <jats:italic>n<\/jats:italic>\n            points,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) edges, and constant dilation, our main result is a data structure that answers (1 + \u03b5)-approximate shortest-path-length queries in constant time. The data structure can be constructed in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) space. This represents the first data structure that answers (1 + \u03b5)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with \u201crounded\u201d obstacles can be answered in constant time. Other applications include query versions of\n            <jats:italic>closest-pair<\/jats:italic>\n            problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + \u03b5)-approximate shortest-path-length queries in constant time for geometric spanner graphs with\n            <jats:italic>m<\/jats:italic>\n            = \u03c9(\n            <jats:italic>n<\/jats:italic>\n            ) edges. The resulting data structure can be constructed in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) space.\n          <\/jats:p>","DOI":"10.1145\/1328911.1328921","type":"journal-article","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T16:08:32Z","timestamp":1207066112000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Approximate distance oracles for geometric spanners"],"prefix":"10.1145","volume":"4","author":[{"given":"Joachim","family":"Gudmundsson","sequence":"first","affiliation":[{"name":"National ICT Australia Ltd., Eveleigh NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Levcopoulos","sequence":"additional","affiliation":[{"name":"Lund University, Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giri","family":"Narasimhan","sequence":"additional","affiliation":[{"name":"Florida International University, Miami, FL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,3,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336213"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263869"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 4th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science","volume":"1136","author":"Arikati S.","unstructured":"Arikati , S. , Chen , D. Z. , Chew , L. P. , Das , G. , Smid , M. , and Zaroliagis , C. D . 1996. Planar spanners and approximate shortest path queries among obstacles in the plane . In Proceedings of the 4th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science , vol. 1136 . Springer, Berlin, 514--528. Arikati, S., Chen, D. Z., Chew, L. P., Das, G., Smid, M., and Zaroliagis, C. D. 1996. Planar spanners and approximate shortest path queries among obstacles in the plane. In Proceedings of the 4th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 1136. Springer, Berlin, 514--528."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796342"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), 271--280","author":"Baswana S.","key":"e_1_2_1_8_1","unstructured":"Baswana , S. , and Sen , S . 2004. Approximate distance oracles for unweighted graphs in \u00d5(n2) time . In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), 271--280 . Baswana, S., and Sen, S. 2004. Approximate distance oracles for unweighted graphs in \u00d5(n2) time. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), 271--280."},{"key":"e_1_2_1_9_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 4th Latin American Symposium on Theoretical Informatics","author":"Bender M. A.","unstructured":"Bender , M. A. , and Farach-Colton , M. 2000. The LCA problem revisited . In Proceedings of the 4th Latin American Symposium on Theoretical Informatics . Lecture Notes in Computer Science , vol. 1776 . Springer , Berlin , 88--94. Bender, M. A., and Farach-Colton, M. 2000. The LCA problem revisited. In Proceedings of the 4th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science, vol. 1776. Springer, Berlin, 88--94."},{"volume-title":"Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), 291--300","author":"Callahan P. B.","key":"e_1_2_1_11_1","unstructured":"Callahan , P. B. , and Kosaraju , S. R . 1993. Faster algorithms for some geometric graph problems in higher dimensions . In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), 291--300 . Callahan, P. B., and Kosaraju, S. R. 1993. Faster algorithms for some geometric graph problems in higher dimensions. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), 291--300."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009390"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), 292--301","author":"Chen D. Z.","year":"1995","unstructured":"Chen , D. Z. 1995 . On the all-pairs Euclidean short path problem . In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), 292--301 . Chen, D. Z. 1995. On the all-pairs Euclidean short path problem. In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA), 292--301."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000675"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796307194"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28402"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261295"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000193"},{"key":"e_1_2_1_20_1","volume-title":"Lecture Notes in Computer Science","volume":"401","author":"Das G.","unstructured":"Das , G. , and Joseph , D . 1989. Which triangulations approximate the complete graph&quest; In Proceedings of the International Symposium on Optimal Algorithms . Lecture Notes in Computer Science , vol. 401 . Springer, Berlin, 168--192. Das, G., and Joseph, D. 1989. Which triangulations approximate the complete graph&quest; In Proceedings of the International Symposium on Optimal Algorithms. Lecture Notes in Computer Science, vol. 401. Springer, Berlin, 168--192."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0961-x"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2925-6"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_42"},{"volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 828--837","author":"Gudmundsson J.","key":"e_1_2_1_27_1","unstructured":"Gudmundsson , J. , Levcopoulos , C. , Narasimhan , G. , and Smid , M . 2002a. Approximate distance oracles for geometric graphs . In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 828--837 . Gudmundsson, J., Levcopoulos, C., Narasimhan, G., and Smid, M. 2002a. Approximate distance oracles for geometric graphs. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 828--837."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 13th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science","volume":"2518","author":"Gudmundsson J.","unstructured":"Gudmundsson , J. , Levcopoulos , C. , Narasimhan , G. , and Smid , M . 2002b. Approximate distance oracles revisited . In Proceedings of the 13th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science , vol. 2518 . Springer, Berlin, 357--368. Gudmundsson, J., Levcopoulos, C., Narasimhan, G., and Smid, M. 2002b. Approximate distance oracles revisited. In Proceedings of the 13th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 2518. Springer, Berlin, 357--368."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90041-X"},{"volume-title":"Algorithms on Strings, Trees and Sequences","author":"Gusfield D.","key":"e_1_2_1_30_1","unstructured":"Gusfield , D. 1997. Algorithms on Strings, Trees and Sequences . Cambridge University Press , Cambridge, UK . Gusfield, D. 1997. Algorithms on Strings, Trees and Sequences. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.263003"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875596"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009323"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187821"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840442"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000216"},{"key":"e_1_2_1_39_1","first-page":"633","article-title":"Geometric shortest paths and network optimization. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds. Elsevier Science, Amsterdam","volume":"24","author":"Mitchell J. S. B.","year":"1998","unstructured":"Mitchell , J. S. B. 1998 . Geometric shortest paths and network optimization. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds. Elsevier Science, Amsterdam , Chapter 24 , 633 -- 701 . Mitchell, J. S. B. 1998. Geometric shortest paths and network optimization. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds. Elsevier Science, Amsterdam, Chapter 24, 633--701.","journal-title":"Chapter"},{"volume-title":"Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, eds","author":"Mitchell J. S. B.","key":"e_1_2_1_40_1","unstructured":"Mitchell , J. S. B. 1997. Shortest paths and networks . In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, eds . CRC Press LLC , Boca Raton, FL , Chapter 24, 445--466. Mitchell, J. S. B. 1997. Shortest paths and networks. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, eds. CRC Press LLC, Boca Raton, FL, Chapter 24, 445--466."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361671"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0063"},{"key":"e_1_2_1_43_1","volume-title":"Computational Geometry: An Introduction","author":"Preparata F. P.","year":"1988","unstructured":"Preparata , F. P. , and Shamos , M. I . 1988 . Computational Geometry: An Introduction . Springer , Berlin . Preparata, F. P., and Shamos, M. I. 1988. Computational Geometry: An Introduction. Springer, Berlin."},{"volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. Lecture Notes in Computer Science. Springer","author":"Pyrga E.","key":"e_1_2_1_44_1","unstructured":"Pyrga , E. , Schulz , F. , Wagner , D. , and Zaroliagis , C . 2004. Experimental comparison of shortest path approaches for timetable information . In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. Lecture Notes in Computer Science. Springer , Berlin, 88--99. Pyrga, E., Schulz, F., Wagner, D., and Zaroliagis, C. 2004. Experimental comparison of shortest path approaches for timetable information. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. Lecture Notes in Computer Science. Springer, Berlin, 88--99."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195991000098"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"volume-title":"Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, eds","author":"Suri S.","key":"e_1_2_1_47_1","unstructured":"Suri , S. 1997. Polygons . In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, eds . CRC Press LLC , Boca Raton, FL , Chapter 23, 429--444. Suri, S. 1997. Polygons. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, eds. CRC Press LLC, Boca Raton, FL, Chapter 23, 429--444."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380798"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Wagner D. and \n      Willhalm T\n  . \n  2003\n  . Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proceedings of the 11th Annual European Symposium on Algorithms (ESA) Lecture Notes in Computer Science vol. \n  2832\n  . \n  Springer Berlin 776--787.  Wagner D. and Willhalm T. 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proceedings of the 11th Annual European Symposium on Algorithms (ESA) Lecture Notes in Computer Science vol. 2832. Springer Berlin 776--787.","DOI":"10.1007\/978-3-540-39658-1_69"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways. Electronic Notes in Theoretical Computer Science","volume":"92","author":"Wagner D.","unstructured":"Wagner , D. , Willhalm , T. , and Zaroliagis , C . 2004. Dynamic shortest path containers . In Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways. Electronic Notes in Theoretical Computer Science , vol. 92 . Elsevier, 65--84. Wagner, D., Willhalm, T., and Zaroliagis, C. 2004. Dynamic shortest path containers. In Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways. Electronic Notes in Theoretical Computer Science, vol. 92. Elsevier, 65--84."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328921","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1328911.1328921","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:03Z","timestamp":1750254963000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328921"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1328911.1328921"],"URL":"https:\/\/doi.org\/10.1145\/1328911.1328921","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}