We study approximating the continuous Fr\u00e9chet distance of two curves with complexity n and m, under the assumption that only one of the two curves is c-packed. Driemel, Har-Peled and Wenk DCG\u201912 studied Fr\u00e9chet distance approximations under the assumption that both curves are c-packed. In $\\mathbb{R}^d$, they prove a $(1 + \\varepsilon)$-approximation in $\\tilde{O}\\!\\left( c{\\frac{n+m}{\\varepsilon}} \\right)$ time. Bringmann and K\u00fcnnemann IJCGA\u201917 improved this to $\\tilde{O}\\!\\left( c{\\frac{n+m}{\\sqrt\\varepsilon}} \\right)$ time, which they showed is near-tight under SETH. Both algorithms have a hidden exponential dependency on the dimension d. Recently, Gudmundsson, Mai, and Wong ISAAC\u201924 studied our setting where only one of the curves is c-packed. They provide an involved $\\tilde{O}((c + \\varepsilon^{-1})(cn\\varepsilon^{-2} + c^{+2}m\\varepsilon^{-7} + \\varepsilon^{-2d-1}))$-time algorithm when the c-packed curve has n vertices and the arbitrary curve has m. In this paper, we show a simple technique to compute a $(1 + \\varepsilon)$-approximation in $\\mathbb{R}^d$ in time ${O}( c{\\frac{n+m}{\\varepsilon}}\\log {\\frac{n+m}{\\varepsilon}})$ when one of the curves is c-packed. Our approach is not only simpler than previous work, but also significantly improves the dependencies on c, $\\varepsilon$, and d (which is only linear). Moreover, it almost matches the asymptotically tight bound for when both curves are c-packed. Our algorithm is robust in the sense that it does not require knowledge of c, nor information about which of the two input curves is c-packed.<\/p>\n","protected":false},"excerpt":{"rendered":"
We study approximating the continuous Fr\u00e9chet distance of two curves with complexity n and m, under the assumption that only one of the two curves is c-packed. Driemel, Har-Peled and Wenk DCG\u201912 studied Fr\u00e9chet distance approximations under the assumption that both curves are c-packed. In $\\mathbb{R}^d$, they prove a $(1 + \\varepsilon)$-approximation in $\\tilde{O}\\!\\left( c{\\frac{n+m}{\\varepsilon}} \\right)$ time. Bringmann and K\u00fcnnemann IJCGA\u201917 improved this to $\\tilde{O}\\!\\left( c{\\frac{n+m}{\\sqrt\\varepsilon}} \\right)$ time, which they […]<\/p>\n","protected":false},"author":14,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[32],"publication-year":[1680],"class_list":["post-43986","publication","type-publication","status-publish","hentry","publication-type-inproceedings","publication-year-1680"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/43986","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/publication"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/14"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/43986\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=43986"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=43986"},{"taxonomy":"publication-year","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-year?post=43986"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}