{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T16:06:29Z","timestamp":1762445189733,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["850979"],"award-info":[{"award-number":["850979"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,7,31]]},"abstract":"<jats:p>\n            The discrete Fr\u00e9chet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fr\u00e9chet distance under translation, which enables detection of similar movement patterns in different spatial domains. For polygonal curves of length\n            <jats:italic>n<\/jats:italic>\n            in the plane, the fastest known algorithm runs in time \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>5<\/jats:sup>\n            ) [12]. This is achieved by constructing an arrangement of disks of size \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            ), and then traversing its faces while updating reachability in a directed grid graph of size\n            <jats:italic>N<\/jats:italic>\n            := \u00d5(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>5<\/jats:sup>\n            ), which can be done in time \u00d5(\u221a\n            <jats:italic>N<\/jats:italic>\n            ) per update [27]. The contribution of this article is two-fold.\n          <\/jats:p>\n          <jats:p>\n            First, although it is an open problem to solve dynamic reachability in directed grid graphs faster than \u00d5(\u221a\n            <jats:italic>N<\/jats:italic>\n            ), we improve this part of the algorithm: We observe that an offline variant of dynamic\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            -reachability in directed grid graphs suffices, and we solve this variant in amortized time \u00d5(\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>1\/3<\/jats:sup>\n            ) per update, resulting in an improved running time of \u00d5(\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>4.66<\/jats:sup>\n            ) for the discrete Fr\u00e9chet distance under translation. Second, we provide evidence that constructing the arrangement of size \u00d5(\n            <jats:italic>N<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            ) is necessary in the worst case by proving a conditional lower bound of\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4 - o(1)<\/jats:sup>\n            on the running time for the discrete Fr\u00e9chet distance under translation, assuming the Strong Exponential Time Hypothesis.\n          <\/jats:p>","DOI":"10.1145\/3460656","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T05:26:33Z","timestamp":1626413193000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Discrete Fr\u00e9chet Distance under Translation"],"prefix":"10.1145","volume":"17","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[{"name":"Saarland University and Max Planck Institute for Informatics, Saarland Informatics Campus, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marvin","family":"K\u00fcNnemann","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarland Informatics Campus, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nusser","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics and Graduate School of Computer Science, Saarland Informatics Campus, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","author":"Abboud Amir","year":"2018","unstructured":"Amir Abboud and Karl Bringmann . 2018 . Tighter connections between formula-sat and shaving logs . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) . Amir Abboud and Karl Bringmann. 2018. Tighter connections between formula-sat and shaving logs. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.58"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214084"},{"volume-title":"Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913)","author":"Agarwal P.","key":"e_1_2_1_4_1","unstructured":"P. Agarwal , R. Ben Avraham , H. Kaplan , and M. Sharir . 2013. Computing the discrete Fr\u00e9chet distance in subquadratic time . In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913) . 156\u2013167. P. Agarwal, R. Ben Avraham, H. Kaplan, and M. Sharir. 2013. Computing the discrete Fr\u00e9chet distance in subquadratic time. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913). 156\u2013167."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116259.3116377"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646515.695842"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201914)","author":"Asano Tetsuo","year":"2014","unstructured":"Tetsuo Asano , David Kirkpatrick , Kotaro Nakagawa , and Osamu Watanabe . 2014 . -Space and polynomial-time algorithm for planar directed graph reachability . In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201914) . 45\u201356. Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, and Osamu Watanabe. 2014. -Space and polynomial-time algorithm for planar directed graph reachability. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201914). 45\u201356."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918)","author":"Ashida Ryo","year":"2018","unstructured":"Ryo Ashida and Kotaro Nakagawa . 2018 . -space algorithm for the grid graph reachability problem . In Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918) . 5:1\u20135:13. Ryo Ashida and Kotaro Nakagawa. 2018. -space algorithm for the grid graph reachability problem. In Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918). 5:1\u20135:13."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140062"},{"key":"e_1_2_1_11_1","first-page":"29","article-title":"The discrete and semicontinuous Fr\u00e9chet distance with shortcuts via approximate distance counting and selection","volume":"11","author":"Avraham Rinat Ben","year":"2015","unstructured":"Rinat Ben Avraham , Omrit Filtser , Haim Kaplan , Matthew J. Katz , and Micha Sharir . 2015 . The discrete and semicontinuous Fr\u00e9chet distance with shortcuts via approximate distance counting and selection . ACM Trans. Algor. 11 , 4 (2015), 29 . Rinat Ben Avraham, Omrit Filtser, Haim Kaplan, Matthew J. Katz, and Micha Sharir. 2015. The discrete and semicontinuous Fr\u00e9chet distance with shortcuts via approximate distance counting and selection. ACM Trans. Algor. 11, 4 (2015), 29.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_12_1","volume-title":"A faster algorithm for the discrete F\u00e9chet distance under translation. ArXiv preprint http:\/\/arxiv.org\/abs\/1501.03724","author":"Avraham Rinat Ben","year":"2015","unstructured":"Rinat Ben Avraham , Haim Kaplan , and Micha Sharir . 2015. A faster algorithm for the discrete F\u00e9chet distance under translation. ArXiv preprint http:\/\/arxiv.org\/abs\/1501.03724 ( 2015 ). Rinat Ben Avraham, Haim Kaplan, and Micha Sharir. 2015. A faster algorithm for the discrete F\u00e9chet distance under translation. ArXiv preprint http:\/\/arxiv.org\/abs\/1501.03724 (2015)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083691"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.180"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 35th International Symposium on Computational Geometry","volume":"129","author":"Bringmann Karl","year":"2019","unstructured":"Karl Bringmann , Marvin K\u00fcnnemann , and Andr\u00c3\u00a9 Nusser . 2019 . Walking the dog fast in practice: Algorithm\u00a0engineering of the F\u00e9chet distance . In Proceedings of the 35th International Symposium on Computational Geometry , Vol. 129 , Gill Barequet and Yusu Wang (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1\u201317:21. DOI:10.4230\/LIPIcs.SoCG. 2019.17 10.4230\/LIPIcs.SoCG.2019.17 Karl Bringmann, Marvin K\u00fcnnemann, and Andr\u00c3\u00a9 Nusser. 2019. Walking the dog fast in practice: Algorithm\u00a0engineering of the F\u00e9chet distance. In Proceedings of the 35th International Symposium on Computational Geometry, Vol. 129, Gill Barequet and Yusu Wang (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 17:1\u201317:21. DOI:10.4230\/LIPIcs.SoCG.2019.17"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195911003652"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.103"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.71"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140064"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.02.008"},{"volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917)","author":"Timothy","key":"e_1_2_1_22_1","unstructured":"Timothy M. Chan and Konstantinos Tsakalidis. 2017. dynamic orthogonal range searching on the ram, revisited . In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917) . 28:1\u201328:13. Timothy M. Chan and Konstantinos Tsakalidis. 2017. dynamic orthogonal range searching on the ram, revisited. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917). 28:1\u201328:13."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"volume-title":"Algorithm\u00a0Theory - SWAT \u201992 (Lecture Notes in Computer Science)","author":"Paul Chew L.","key":"e_1_2_1_24_1","unstructured":"L. Paul Chew and Klara Kedem . 1992. Improvements on geometric pattern matching problems . In Algorithm\u00a0Theory - SWAT \u201992 (Lecture Notes in Computer Science) , Otto Nurmi and Esko Ukkonen (Eds.). Springer Berlin , 318\u2013325. L. Paul Chew and Klara Kedem. 1992. Improvements on geometric pattern matching problems. In Algorithm\u00a0Theory - SWAT \u201992 (Lecture Notes in Computer Science), Otto Nurmi and Esko Ukkonen (Eds.). Springer Berlin, 318\u2013325."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7537"},{"key":"e_1_2_1_26_1","first-page":"193","article-title":"Geodesic Fr\u00e9chet distance inside a simple polygon","volume":"7","author":"Cook A. F.","year":"2010","unstructured":"A. F. Cook and Carola Wenk . 2010 . Geodesic Fr\u00e9chet distance inside a simple polygon . ACM Trans. Algor. 7 , 1 (2010), 193 \u2013 204 . A. F. Cook and Carola Wenk. 2010. Geodesic Fr\u00e9chet distance inside a simple polygon. ACM Trans. Algor. 7, 1 (2010), 193\u2013204.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_53"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/120865112"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140063"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901)","author":"Efrat Alon","year":"2001","unstructured":"Alon Efrat , Piotr Indyk , and Suresh Venkatasubramanian . 2001 . Pattern matching for sets of segments . In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901) . 295\u2013304. Alon Efrat, Piotr Indyk, and Suresh Venkatasubramanian. 2001. Pattern matching for sets of segments. In Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901). 295\u2013304."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917)","volume":"77","author":"Fan Chenglin","year":"2017","unstructured":"Chenglin Fan and Benjamin Raichel . 2017 . Computing the Fr\u00e9chet gap distance . In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917) , Vol. 77 . 42:1\u201342:16. Chenglin Fan and Benjamin Raichel. 2017. Computing the Fr\u00e9chet gap distance. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917), Vol. 77. 42:1\u201342:16."},{"key":"e_1_2_1_33_1","volume-title":"Katz","author":"Filtser Omrit","year":"2015","unstructured":"Omrit Filtser and Matthew J . Katz . 2015 . The Discrete Fr\u00e9chet Gap. ArXiv preprint http:\/\/arxiv.org\/abs\/1506.04861 (2015). Omrit Filtser and Matthew J. Katz. 2015. The Discrete Fr\u00e9chet Gap. ArXiv preprint http:\/\/arxiv.org\/abs\/1506.04861 (2015)."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201918) (Leibniz International Proceedings in Informatics (LIPIcs)), David Eppstein (Ed.)","volume":"101","author":"Filtser Omrit","year":"2018","unstructured":"Omrit Filtser and Matthew J. Katz . 2018. Algorithms for the discrete Fr\u00e9chet distance under translation . In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201918) (Leibniz International Proceedings in Informatics (LIPIcs)), David Eppstein (Ed.) , Vol. 101 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 20:1\u201320:14. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SWAT. 2018 .20 Omrit Filtser and Matthew J. Katz. 2018. Algorithms for the discrete Fr\u00e9chet distance under translation. In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201918) (Leibniz International Proceedings in Informatics (LIPIcs)), David Eppstein (Ed.), Vol. 101. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 20:1\u201320:14. DOI:DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2018.20"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808675"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189323"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513414"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055480"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720008003278"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009223"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.09.008"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9758-3"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322410"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436722"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1055715.1646513"},{"volume-title":"Proceedings of the 7th International Conference on Computer Vision (ICCV\u201999)","author":"Mario","key":"e_1_2_1_48_1","unstructured":"Mario E. Munich and Pietro Perona. 1999. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification . In Proceedings of the 7th International Conference on Computer Vision (ICCV\u201999) . 108\u2013115. Mario E. Munich and Pietro Perona. 1999. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification. In Proceedings of the 7th International Conference on Computer Vision (ICCV\u201999). 108\u2013115."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02716804"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57273-2_72"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460656","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460656","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:57Z","timestamp":1750193277000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460656"}},"subtitle":["Conditional Hardness and an Improved Algorithm"],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3460656"],"URL":"https:\/\/doi.org\/10.1145\/3460656","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}