{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T20:10:47Z","timestamp":1781381447617,"version":"3.54.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,25]],"date-time":"2023-03-25T00:00:00Z","timestamp":1679702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CF-1637546, CCF-1815316"],"award-info":[{"award-number":["CF-1637546, CCF-1815316"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["592\/17, 810\/21"],"award-info":[{"award-number":["592\/17, 810\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Independent Research Fund Denmark","award":["7027-00050B"],"award-info":[{"award-number":["7027-00050B"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>\n            We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between\n            <jats:italic>space<\/jats:italic>\n            <jats:italic>S<\/jats:italic>\n            and\n            <jats:italic>query time<\/jats:italic>\n            <jats:italic>Q<\/jats:italic>\n            , and since the mid-1990s all results had polynomial time-space tradeoffs, e.g.,\n            <jats:italic>Q<\/jats:italic>\n            = ~ \u0398(\n            <jats:italic>n\/\u221a S<\/jats:italic>\n            ) or\n            <jats:italic>Q<\/jats:italic>\n            = ~\u0398(\n            <jats:italic>\n              n\n              <jats:sup>5\/2<\/jats:sup>\n              \/S\n              <jats:sup>3\/2<\/jats:sup>\n            <\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            In this article we show that there is no polynomial tradeoff between time and space and that it is possible to\n            <jats:italic>simultaneously<\/jats:italic>\n            achieve almost optimal space\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1+\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            and almost optimal query time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            . More precisely, we achieve the following space-time tradeoffs:\n            <jats:list list-type=\"none\">\n              <jats:list-item>\n                <jats:p>\n                  <jats:italic>n<\/jats:italic>\n                  <jats:sup>\n                    1+\n                    <jats:italic>o<\/jats:italic>\n                    (1)\n                  <\/jats:sup>\n                  space and log\n                  <jats:sup>\n                    2+\n                    <jats:italic>o<\/jats:italic>\n                    (1)\n                  <\/jats:sup>\n                  <jats:italic>n<\/jats:italic>\n                  query time,\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:p>\n                  <jats:italic>n<\/jats:italic>\n                  log\n                  <jats:sup>\n                    2+\n                    <jats:italic>o<\/jats:italic>\n                    (1)\n                  <\/jats:sup>\n                  <jats:italic>n<\/jats:italic>\n                  space and\n                  <jats:italic>n<\/jats:italic>\n                  <jats:sup>\n                    <jats:italic>o<\/jats:italic>\n                    (1)\n                  <\/jats:sup>\n                  query time,\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:p>\n                  <jats:italic>n<\/jats:italic>\n                  <jats:sup>\n                    4\/3+\n                    <jats:italic>o<\/jats:italic>\n                    (1)\n                  <\/jats:sup>\n                  space and log\n                  <jats:sup>\n                    1+\n                    <jats:italic>o<\/jats:italic>\n                    (1)\n                  <\/jats:sup>\n                  <jats:italic>n<\/jats:italic>\n                  query time.\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>\n          <jats:p>\n            We reduce a distance query to a variety of\n            <jats:italic>point location<\/jats:italic>\n            problems in additively weighted\n            <jats:italic>Voronoi diagrams<\/jats:italic>\n            and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.\n          <\/jats:p>","DOI":"10.1145\/3580474","type":"journal-article","created":{"date-parts":[[2023,3,25]],"date-time":"2023-03-25T09:46:02Z","timestamp":1679737562000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Almost Optimal Exact Distance Oracles for Planar Graphs"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6024-1557","authenticated-orcid":false,"given":"Panagiotis","family":"Charalampopoulos","sequence":"first","affiliation":[{"name":"Birkbeck, University of London, London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6993-5440","authenticated-orcid":false,"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1891-9897","authenticated-orcid":false,"given":"Yaowei","family":"Long","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9262-1821","authenticated-orcid":false,"given":"Shay","family":"Mozes","sequence":"additional","affiliation":[{"name":"Reichmann University, Herzliya, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0495-3904","authenticated-orcid":false,"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4510-7552","authenticated-orcid":false,"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[{"name":"University of Haifa, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3699-7821","authenticated-orcid":false,"given":"Christian","family":"Wulff-Nilsen","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,3,25]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24100-0_39"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_5"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61680-2_79"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/10719839_9"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2003.05.002"},{"issue":"3","key":"e_1_3_4_7_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2684068","article-title":"Min st-cut oracle for planar graphs with near-linear preprocessing time","volume":"11","author":"Borradaile Glencora","year":"2015","unstructured":"Glencora Borradaile, Piotr Sankowski, and Christian Wulff-Nilsen. 2015. Min st-cut oracle for planar graphs with near-linear preprocessing time. ACM Transactions on Algorithms 11, 3 (2015), 1\u201329.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_4_8_2","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/978-3-642-22300-6_25","volume-title":"Proceedings of the 12th Int\u2019l Symposium on Algorithms and Data Structures (WADS\u201911)","author":"Brodal Gerth St\u00f8lting","year":"2011","unstructured":"Gerth St\u00f8lting Brodal, Pooya Davoodi, and S Srinivasa Rao. 2011. Path minima queries in dynamic weighted trees. In Proceedings of the 12th Int\u2019l Symposium on Algorithms and Data Structures (WADS\u201911). 290\u2013301."},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_12"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9459-0"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3218821"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/120864271"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/090766863"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00570-z"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316316"},{"key":"e_1_3_4_16_2","volume-title":"Proceedings of the 48th Int\u2019l Colloq. on Algorithms, Languages, and Programming (ICALP\u201921)","author":"Charalampopoulos Panagiotis","year":"2021","unstructured":"Panagiotis Charalampopoulos, Pawe\u0142 Gawrychowski, Shay Mozes, and Oren Weimann. 2021. An almost optimal edit distance oracle. In Proceedings of the 48th Int\u2019l Colloq. on Algorithms, Languages, and Programming (ICALP\u201921)."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.09.008"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3511541"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746562"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335359"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.93"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51542-9_8"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62559-3_14"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188904"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.007"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_4_31_2","article-title":"Truly subquadratic exact distance oracles with constant query time for planar graphs","volume":"2009","author":"Fredslund-Hansen Viktor","year":"2020","unstructured":"Viktor Fredslund-Hansen, Shay Mozes, and Christian Wulff-Nilsen. 2020. Truly subquadratic exact distance oracles with constant query time for planar graphs. CoRR abs\/2009.14716. (2020). arxiv:2009.14716https:\/\/arxiv.org\/abs\/2009.14716.","journal-title":"CoRR"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.33"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.34"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32686-9_20"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.08.024"},{"key":"e_1_3_4_36_2","article-title":"Still simpler static level ancestors","volume":"2005","author":"Hagerup Torben","year":"2020","unstructured":"Torben Hagerup. 2020. Still simpler static level ancestors. CoRR abs\/2005.11188. (2020). arxiv:2005.11188https:\/\/arxiv.org\/abs\/2005.11188.","journal-title":"CoRR"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"issue":"2","key":"e_1_3_4_41_2","first-page":"26:1\u201326:42","article-title":"Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications","volume":"13","author":"Kaplan Haim","year":"2017","unstructured":"Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir. 2017. Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications. ACM Trans. Algorithms 13, 2 (2017), 26:1\u201326:42.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.17"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22006-7_12"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.40"},{"key":"e_1_3_4_45_2","first-page":"820","volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902)","author":"Klein Philip N.","year":"2002","unstructured":"Philip N. Klein. 2002. Preprocessing an undirected planar network to enable fast approximate distance queries. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902). 820\u2013827."},{"key":"e_1_3_4_46_2","first-page":"146","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Klein Philip N.","year":"2005","unstructured":"Philip N. Klein. 2005. Multiple-source shortest paths in planar graphs. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). 146\u2013155. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070454."},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488672"},{"key":"e_1_3_4_48_2","first-page":"155","volume-title":"Proceedings of the 19th Annual European Symposium on Algorithms (ESA\u201911)","author":"Lacki Jakub","year":"2011","unstructured":"Jakub Lacki and Piotr Sankowski. 2011. Min-cuts and shortest cycles in planar graphs in \\({O}(n\\log \\log n)\\) time. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA\u201911). 155\u2013166."},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00044"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_4_51_2","first-page":"2517","volume-title":"Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921)","author":"Long Yaowei","year":"2021","unstructured":"Yaowei Long and Seth Pettie. 2021. Planar distance oracles with better time-space tradeoffs. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921). 2517\u20132536."},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3483425"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90030-9"},{"key":"e_1_3_4_54_2","first-page":"477","volume-title":"Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Mozes Shay","year":"2018","unstructured":"Shay Mozes, Kirill Nikolaev, Yahav Nussbaum, and Oren Weimann. 2018. Minimum cut of directed planar graphs in \\({O}(n \\log \\log n)\\) time. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918). 477\u2013494."},{"key":"e_1_3_4_55_2","first-page":"209","volume-title":"Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Mozes Shay","year":"2012","unstructured":"Shay Mozes and Christian Sommer. 2012. Exact distance oracles for planar graphs. In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912). 209\u2013222."},{"key":"e_1_3_4_56_2","first-page":"206","volume-title":"Proceedings of the 18th Annual European Symposium on Algorithms (ESA\u201910)","author":"Mozes Shay","year":"2010","unstructured":"Shay Mozes and Christian Wulff-Nilsen. 2010. Shortest paths in planar graphs with real lengths in \\({O}(n\\log ^2 n\/\\) \\(\\log \\log n)\\) time. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA\u201910). 206\u2013217."},{"key":"e_1_3_4_57_2","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1007\/978-3-642-22300-6_54","volume-title":"Proceedings 12th Int\u2019l Workshop on Algorithms and Data Structures (WADS\u201911)","author":"Nussbaum Yahav","year":"2011","unstructured":"Yahav Nussbaum. 2011. Improved distance queries in planar graphs. In Proceedings 12th Int\u2019l Workshop on Algorithms and Data Structures (WADS\u201911). 642\u2013653."},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","DOI":"10.1137\/11084128X"},{"key":"e_1_3_4_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.27"},{"key":"e_1_3_4_63_2","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02940617","article-title":"Neuer Beweis f\u00fcr die Invarianz der Dimensionszahl und des Gebietes","volume":"6","author":"Sperner E.","year":"1928","unstructured":"E. Sperner. 1928. Neuer Beweis f\u00fcr die Invarianz der Dimensionszahl und des Gebietes. Abh. Math. Semin. Hamburg. Univ. Bd. 6 (1928), 265\u2013272.","journal-title":"Abh. Math. Semin. Hamburg. Univ."},{"key":"e_1_3_4_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_3_4_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_3_4_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"},{"key":"e_1_3_4_67_2","doi-asserted-by":"crossref","unstructured":"D. E. Willard. 1983. Log-logarithmic worst-case range queries are possible in space  \\(\\Theta (N)\\) . Information Processing Letters 17 2 (1983) 81\u201384.","DOI":"10.1016\/0020-0190(83)90075-3"},{"key":"e_1_3_4_68_2","volume-title":"Algorithms for Planar Graphs and Graphs in Metric Spaces","author":"Wulff-Nilsen Christian","year":"2010","unstructured":"Christian Wulff-Nilsen. 2010. Algorithms for Planar Graphs and Graphs in Metric Spaces. Ph.D. Dissertation. University of Copenhagen."},{"key":"e_1_3_4_69_2","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1137\/1.9781611974331.ch26","volume-title":"Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Wulff-Nilsen Christian","year":"2016","unstructured":"Christian Wulff-Nilsen. 2016. Approximate distance oracles for planar graphs with improved query time-space tradeoff. In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). 351\u2013362."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580474","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:42Z","timestamp":1750178262000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,25]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3580474"],"URL":"https:\/\/doi.org\/10.1145\/3580474","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,25]]},"assertion":[{"value":"2021-05-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}