{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:55Z","timestamp":1750309315585,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T00:00:00Z","timestamp":1722816000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["313421352"],"award-info":[{"award-number":["313421352"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>\n            The Fr\u00e9chet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min\u2013max formulation that considers all orientation-preserving bijective mappings between the two curves. Because of its susceptibility to noise, Driemel and Har-Peled introduced the shortcut Fr\u00e9chet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterised version of this problem, where the number of shortcuts is bounded by a parameter\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . The corresponding decision problem can be stated as follows: Given two polygonal curves\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(T\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(B\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            of at most\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            vertices, a parameter\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and a distance threshold\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\delta\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , is it possible to introduce\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            shortcuts along\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(B\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            such that the Fr\u00e9chet distance of the resulting curve and the curve\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(T\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is at most\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\delta\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            ? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (1) there exists a decision algorithm with running time in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(kn^{2k+2}\\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            ; (2) assuming the exponential-time hypothesis (ETH), there exists no algorithm with running time bounded by\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(n^{o(k)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . In contrast, we also show that efficient approximate decider algorithms are possible, even when\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is large. We present a\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((3+\\varepsilon)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximate decider algorithm with running time in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal{O}(kn^{2}\\log^{2}n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for fixed\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varepsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . In addition, we can show that, if\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is a constant and the two curves are\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(c\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -packed for some constant\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(c\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , then the approximate decider algorithm runs in near-linear time.\n          <\/jats:p>","DOI":"10.1145\/3663762","type":"journal-article","created":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T12:45:03Z","timestamp":1716468303000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Computing the\n            <i>k<\/i>\n            -Shortcut Fr\u00e9chet Distance"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8259-1187","authenticated-orcid":false,"given":"Jacobus","family":"Conradi","sequence":"first","affiliation":[{"name":"Institute for Computer Science V, University of Bonn, Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1943-2589","authenticated-orcid":false,"given":"Anne","family":"Driemel","sequence":"additional","affiliation":[{"name":"Hausdorff Center for Mathematics, Bonn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,5]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2019.50"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530830"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_8"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700222"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v7i2a4"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-008-0147-3"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9878-7"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.71"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.179"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3559764"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582144"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.01.002"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00234-2"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.30"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1811019"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03018603"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54945-5_59"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766282"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.862197"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.86"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219054"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00574-9"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SMA.2001.923389"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3663762","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3663762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:53Z","timestamp":1750291433000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3663762"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,5]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3663762"],"URL":"https:\/\/doi.org\/10.1145\/3663762","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,8,5]]},"assertion":[{"value":"2022-11-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-30","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}