{"id":38955,"date":"2026-08-21T15:27:30","date_gmt":"2026-08-21T15:27:30","guid":{"rendered":"https:\/\/lamarr-institute.org\/publication\/the-quick-dog-jumps-the-log\/"},"modified":"2026-09-17T11:16:45","modified_gmt":"2026-09-17T11:16:45","slug":"the-quick-dog-jumps-the-log","status":"publish","type":"publication","link":"https:\/\/lamarr-institute.org\/de\/publication\/the-quick-dog-jumps-the-log\/","title":{"rendered":"The Quick Dog Jumps the Log"},"content":{"rendered":"<p>We give linear-time, and thus optimal, (1+{$\\epsilon$})-approximation algorithms for numerous variants of the Fr\u00e9chet distance between c-packed curves (where c {$\\in$} O(1)), removing an additional log factor that was present in previous algorithms. The key to our new algorithms is a linear-size approximation of the elevation function, which uses a decomposition of the domain into rectangles, and a careful implicit dynamic programming on this decomposition. The algorithm extends to the strong, weak, discrete, and continuous Fr\u00e9chet distances with a running time of roughly O(cn\/{$\\epsilon$}). The c-packedness assumption is used only in the analysis, and the algorithm is simple and should work efficiently for other inputs.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>We give linear-time, and thus optimal, (1+{$\\epsilon$})-approximation algorithms for numerous variants of the Fr\u00e9chet distance between c-packed curves (where c {$\\in$} O(1)), removing an additional log factor that was present in previous algorithms. The key to our new algorithms is a linear-size approximation of the elevation function, which uses a decomposition of the domain into rectangles, and a careful implicit dynamic programming on this decomposition. The algorithm extends to the [&hellip;]<\/p>\n","protected":false},"author":14,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[30],"class_list":["post-38955","publication","type-publication","status-publish","hentry","publication-type-article"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/38955","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\/38955\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=38955"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=38955"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}