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

CREATORJacobus Conradi, Ivor van der Hoog, Frederikke Uldahl, Eva Rotenberg
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58827
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text