{"id":32555,"date":"2026-01-21T17:02:12","date_gmt":"2026-01-21T17:02:12","guid":{"rendered":"https:\/\/lamarr-institute.org\/publication\/approximating-the-frechet-distance-in-graphswith-low-highway-dimension\/"},"modified":"2026-06-08T13:21:00","modified_gmt":"2026-06-08T13:21:00","slug":"approximating-the-frechet-distance-in-graphswith-low-highway-dimension","status":"publish","type":"publication","link":"https:\/\/lamarr-institute.org\/de\/publication\/approximating-the-frechet-distance-in-graphswith-low-highway-dimension\/","title":{"rendered":"Approximating the Fr\u00e9chet Distance in Graphswith Low Highway Dimension"},"content":{"rendered":"<p>In this paper, we study algorithms for the discrete Fr\u00e9chet distance in graphs with low highway dimension. We describe a $(5\\sqrt{3} + \\varepsilon)$-approximation algorithm for the Fr\u00e9chet distance between a shortest path $P$ with $n$ vertices and an arbitrary walk $Q$ with $m$ vertices in a graph $G = (V, E)$. The algorithm makes use of a collection of sparse shortest paths hitting sets which are precomputed for the graph $G$. After preprocessing, the algorithm has running time $O\\left(n \\log D + m(h \\log h \\log D)^2\\right)$, where $h$ is the highway dimension and $D$ is the diameter of $G$. The preprocessing for the graph is polynomial in $\\lvert G \\rvert$ and $1 \/ \\log(1 + \\varepsilon)$ and uses $O\\left(\\lvert V \\rvert \\log D \\left(1 \/ \\log(1 + \\varepsilon) + h \\log h\\right)\\right)$ space.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In this paper, we study algorithms for the discrete Fr\u00e9chet distance in graphs with low highway dimension. We describe a $(5\\sqrt{3} + \\varepsilon)$-approximation algorithm for the Fr\u00e9chet distance between a shortest path $P$ with $n$ vertices and an arbitrary walk $Q$ with $m$ vertices in a graph $G = (V, E)$. The algorithm makes use of a collection of sparse shortest paths hitting sets which are precomputed for the graph [&hellip;]<\/p>\n","protected":false},"author":12,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[32],"class_list":["post-32555","publication","type-publication","status-publish","hentry","publication-type-inproceedings"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32555","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\/12"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32555\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=32555"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=32555"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}