Near-tight Bounds for Computing the Fréchet Distance in d d -Dimensional Grid Graphs and the Implications for λ \lambda -low Dense Curves
Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl, Eva Rotenberg · 2026
Read Near-tight Bounds for Computing the Fréchet Distance in d d -Dimensional Grid Graphs and the Implications for λ \lambda -low Dense Curves by Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl, Eva Rotenberg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24135.txt.
Introduction
Conradi, Van der Hoog, Uldahl, and Rotenberg give near-tight bounds for computing Fréchet distance between lambda-low-density curves, the broadest realistic class. In such curves every ball meets only a bounded number of long edges. Their approximation algorithm for continuous and discrete Fréchet distance rests on a tight simplification property: simplifying a low-density curve preserves low density with a sharp bound. Lower bounds under the Orthogonal Vectors Hypothesis show the dependence on size and density is optimal, and the techniques extend to map matching.
Catalog record
| CREATOR | Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl, Eva Rotenberg |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58827 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.24135
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Near-tight Bounds for Computing the Fréchet Distance in d d -Dimensional Grid Graphs and the Implications for λ \lambda -low Dense Curves Jacobus Conradi, Ivor van der Hoog, Frederikke Uldahl, Eva Rotenberg Abstract The Fréchet distance is a popular distance measure between trajectories or curves in space, or between walks in graphs. We study computing the Fréchet distance between walks in the d d -dimensional grid graphs, i.e. ℤ d \mathbb{Z}^{d} where points share an edge if they differ by one in one coordinate. We give an algorithm, that for two simple paths on n n vertices, ( 1 + ε ) (1+\varepsilon) -approximates the Fréchet distance in time O ~ ( ( n ε ) 2 − 2 / d + n ) \widetilde{O}((\frac{n}{\varepsilon})^{2-2/d}+n) . We complement this by a near-matching fine-grained lower bound: for constant dimensions d ≥ 3 d\geq 3 , there is no O ( ( ε 2 / d ( n ε ) 2 − 2 / d ) 1 − δ ) O((\varepsilon^{2/d}(\frac{n}{\varepsilon})^{2-2/d})^{1-\delta}) algorithm for any δ > 0 \delta>0 unless the Orthogonal Vector Hypothesis fails. Thus, our results are tight up to a factor ε 2 / d \varepsilon^{2/d} and log ( n ) \log(n) -factors. We extend our results to imbalanced lower and upper bounds, where the curves have n n and m m vertices respectively, and also obtain near-tight bounds. Driemel, Har-Peled and Wenk [DCG’12] studied realistic assumptions for curves to speed up Fréchet distance computation. One of these assumptions is λ \lambda -low density and they can compute a ( 1 + ε ) (1+\varepsilon) -approximation between λ \lambda -low dense curves in time O ~ ( ε − 2 λ 2 n 2 ( 1 − 1 / d ) ) \tilde{O}(\varepsilon^{-2}\lambda^{2}n^{2(1-1/d)}) . By adapting our lower bound, we show that their algorithm has a tight dependency on n n and a tight dependency on ε \varepsilon as d d goes to infinity. A gap remains in terms of λ \lambda . Department of Computer Science, University of Copenhagen, [email protected]://orcid.org/0000-0002-8259-1187 IT University of Copenhagen, [email protected] https://orcid.org/0009-0006-2624-0231 IT University of Copenhagen, [email protected]://orcid.org/0009-0003-2279-9239 IT University of Copenhagen, [email protected] https://orcid.org/0000-0001-5853-7909 We thank Sampson Wong for pointing us to the implications of our results for simple paths to \lambda -low density curves. ccs Theory of computation Computational geometry keywords Fréchet Distance, Fine-grained Complexity, Grid Graphs † † runningtitle: Fréchet Distance in d -Dimensional Grid Graphs † † runningauthor: J. Conradi, I. van der Hoog, F. Uldahl, E. Rotenberg † † copyright: J. Conradi, I. van der Hoog, F. Uldahl, E. Rotenberg † † funding: This research is supported by the VILLUM Foundation grant (VIL37507) “Efficient Recomputations for Changeful Problems”, the Danmarks Frie Forskningsfond Case no. 4251-00004B, and the Carlsberg Foundation, grant CF24-1929. Figure 1: A hand-drawn illustration of the discrete and continuous Fréchet distance in 3 D. 1 Introduction The Fréchet distance is a widely recognised measure of similarity between two curves or trajectories. Conceptually, it can be considered the shortest leash length needed to connect a human walking along one curve and a dog walking along the other, with both moving forward without backtracking (see Figure 1 ). The Fréchet distance is used in various real-life applications, including signature verification [ 34 ] , the study of coastline retrievals [ 33 ] , map-matching [ 39 ] , protein structures [ 30 ] , air traffic [ 5 ] , and trajectory analysis and clustering [ 11 , 6 , 9 , 32 , 36 , 31 , 21 , 1 , 37 , 42 , 27 , 10 ] . Alt and Godau [ 2 ] show a O(nm\log(n+m)) -time algorithm for computing the Fréchet distance between two polygonal curves with n and m vertices. Since then, there have been polylogarithmic-time improvements [ 13 , 16 ] , but there is strong evidence that significantly faster algorithms cannot exist. Bringmann [ 8 ] proved that, under the Strong Exponential Time Hypothesis, no strongly subquadratic algorithm (i.e., with running time O((nm)^{1-\delta}) for any \delta>0 ) exists to compute a 1.001 approximation of the Fréchet distance between curves of complexity n and m . Buchin, Ophelders, and Speckmann [ 14 ] rule out a (3-\varepsilon) -approximation in time O((n)^{2-\delta}) between two n -vertex curves in \mathbb{R}^{1} and recently, Blank [ 4 ] rules out a (1+\sqrt{2}-\varepsilon) -approximation (resp. (3-\varepsilon) -approximation) of the Fréchet distance between curves of complexity n and m in \mathbb{R}^{2} under the \ell_{2} -norm (resp. \ell_{\infty} -norm) in time O((nm)^{1-\delta}) . Cheng, Huang, and Zhang [ 15 ] obtain a randomised (7+\varepsilon) -approximation in \tilde{O}(nm^{0.99}) time. Restricted curve classes. To obtain strongly subquadratic-time algorithms, one therefore has to restrict the input. Gudmundsson, Mirzanezhad, Mohades, and Wenk [ 26 ] consider the special case where the input curves consist exclusively of sufficiently long edges relative to their Fréchet distance, and gave a near-linear time exact algorithm. Another way of obtaining subquadratic results is to impose so-called realistic assumptions on the input — I.e., to restrict the curve to not have geometric traits that are considered unrealistic. Examples include \kappa -straight and \kappa -bounded curves [ 3 ] , \lambda -low dense curves [ 35 ] , and c -packed curves [ 20 ] . Driemel, Har-Peled and Wenk [ 20 ] showed, for these classes of curves, a near-linear time algorithm to compute a (1+\varepsilon) -approximation of the Fréchet distance. For c -packed curves (and therefore c -straight and c -bounded curves) they can decide whether the Fréchet distance between two curves is at most \Delta in time O(\frac{c}{\varepsilon}n) . Bringmann and Künnemann [ 7 ] improved the running time to O(\frac{c}{\sqrt{\varepsilon}}n) , and gave a matching lower bound conditioned on the Orthogonal Vector Hypothesis. Gudmundsson, Mai, and Wong [ 25 ] showed that it suffices to assume that one curve is c -packed and show a \tilde{O}(c^{3}\varepsilon^{-8}(n+m)) -time algorithm. Conradi, van der Hoog, van der Horst, and Ophelders [ 17 ] improve this running time to O(\frac{c}{\varepsilon}n) . \lambda -low dense curves. The realism assumption of \lambda -low density is of particular relevance to this paper. A collection of edges in \mathbb{R}^{d} is \lambda -low-density if for any ball B in \mathbb{R}^{d} , the number of edges of length at least \mathrm{radius}(B) that intersect B is at most \lambda . It is a popular realism assumption to speed up computations [ 35 , 20 , 24 , 12 , 28 , 29 , 19 ] with one compelling feature: planar grid graphs are c -packed for c\in\Theta(n) but they are O(1) -low dense. Driemel, Har-Peled and Wenk [ 20 ] show a \tilde{O}(\varepsilon^{-2}\lambda^{2}n^{2(1-1/d)}) -time algorithm to compute a (1+\varepsilon) -approximation of the Fréchet distance between two n -vertex \lambda -low dense curves in \mathbb{R}^{d} , which makes it the only realism assumption discussed in [ 20 ] where the running time exponent depends on d . Fréchet distance in grid graphs. In this paper, we show near-tight bounds for approximating the discrete and continuous Fréchet distance in d -dimensional grid graphs. Driemel, van der Hoog, and Rotenberg [ 22 ] first studied the Fréchet distance in graphs. Their input consists of a