Faster Fréchet Distance under Transformations
Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, Sampson Wong · 2025
Read Faster Fréchet Distance under Transformations by Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, Sampson Wong (2025) 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-2501-12814.txt.
Introduction
The Fréchet distance measures how far apart two routes lie, like a walker and a dog on a leash. Kevin Buchin and co-authors ask in 2025 how fast one can decide whether shifting one curve can bring the distance under a threshold. For plane translations they give an algorithm running in just under n-to-the-seven-and-a-third time, beating the old n-to-the-eighth.
The result stretches to any family of transformations described by rational formulas: rotations, scalings, and full affine maps included. The running time grows with the family's degrees of freedom by a clean formula.
Catalog record
| CREATOR | Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, Sampson Wong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-12814
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Faster Fréchet Distance under Transformations Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, Sampson Wong Abstract We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π \pi and σ \sigma of total complexity n n and a threshold δ ≥ 0 \delta\geq 0 , we present an 𝒪 ~ ( n 7 + 1 3 ) \tilde{\mathcal{O}}(n^{7+\frac{1}{3}}) time algorithm to determine whether there exists a translation t ∈ ℝ 2 t\in\mathbb{R}^{2} such that the Fréchet distance between π \pi and σ + t \sigma+t is at most δ \delta . This improves on the previous best result, which is an 𝒪 ( n 8 ) \mathcal{O}(n^{8}) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class 𝒯 \mathcal{T} of rationally parametrized transformations with k k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ 𝒯 \tau\in\mathcal{T} such that the Fréchet distance between π \pi and τ ( σ ) \tau(\sigma) is at most δ \delta in 𝒪 ~ ( n 3 k + 4 3 ) \tilde{\mathcal{O}}(n^{3k+\frac{4}{3}}) time. Technical University of Dortmund, [email protected]://orcid.org/0000-0002-3022-7877 Ruhr University Bochum, [email protected]://orcid.org/0000-0002-3446-4343 University of Sydney, [email protected]://orcid.org/0000-0003-3417-5303 Université Côte d’Azur, CNRS, Inria, [email protected]://orcid.org/0000-0002-6349-869XThis work was supported by the French government through the France 2030 investment plan managed by the National Research Agency (ANR), as part of the Initiative of Excellence of Université Côte d’Azur under reference number ANR-15-IDEX-01. BARC, University of Copenhagen, [email protected]://orcid.org/0000-0003-3803-3804 ccs Theory of computation Computational geometry keywords Fréchet distance, curve similarity, shape matching † † runningauthor: K. Buchin, M. Buchin, Z. Huang, A. Nusser, S. Wong † † copyright: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, Sampson Wong 1 Introduction Many applications require determining the similarity of two geometric shapes, disregarding their location or orientation. More specifically, shape matching asks for the distance between two shapes if we allow the shapes to be transformed to minimize their distance [ 1 , 3 , 53 ] . Transformations may include translations, rotations, scaling, or a combination thereof. In this paper, we focus on polygonal curves under the Fréchet distance. Curves occur in many applications and need to be matched whenever they describe a local pattern, for example to recognize handwritten characters [ 47 ] or trademarks [ 5 ] . The Fréchet distance is arguably the most popular distance measure for curves in computational geometry. There has been significant algorithmic progress on the Fréchet distance, for instance, most recently on approximation [ 30 , 50 , 51 ] , data structures [ 6 , 12 , 17 , 26 , 36 , 37 , 41 , 40 ] , algorithm engineering [ 8 , 18 , 33 , 15 , 13 ] , simplification [ 11 , 27 , 49 , 52 ] , clustering [ 16 , 19 , 25 , 42 , 46 , 20 ] , Fréchet variants [ 21 , 22 , 23 , 32 , 35 , 38 , 39 ] , and its complexity in general [ 10 , 24 , 29 , 28 ] . The Fréchet distance under translation is defined as the minimum Fréchet distance for any translation of the curves. Computing the Fréchet distance under translations was first studied by Efrat, Indyk and Venkatasubramanian [ 34 ] and by Alt, Knauer and Wenk [ 4 , 45 , 54 ] . For two curves of total complexity n in \mathbb{R}^{2} , an \tilde{\mathcal{O}}(n^{10}) time algorithm 1 1 1 By \tilde{\mathcal{O}}(\cdot) we hide (poly-)logarithmic factors in n . for the Fréchet distance under translation was presented in [ 34 ] , and an \tilde{\mathcal{O}}(n^{8}) time algorithm was presented in [ 4 ] . Wenk [ 54 ] generalized the approach in [ 4 ] to higher dimensions and a wide range of other transformations, e.g., for rotations or scalings in 2D in \tilde{\mathcal{O}}(n^{5}) time, or for affine transformations in d dimensions in \tilde{\mathcal{O}}(n^{3(d^{2}+d)+2}) time. Despite significant algorithmic progress on various aspects of the Fréchet distance, no faster algorithms for computing the (continuous) Fréchet distance under transformations have been developed until now. In contrast, for computing the discrete Fréchet distance under translation, first an \tilde{\mathcal{O}}(n^{6}) -time algorithm [ 43 ] was developed, then an \tilde{\mathcal{O}}(n^{5}) -time algorithm [ 7 ] , and more lately an \tilde{\mathcal{O}}(n^{4+\frac{2}{3}}) -time algorithm [ 14 ] . Our Contribution In this paper, we present the first progress on the Fréchet distance under transformations since its introduction [ 4 , 34 , 45 , 54 ] . Similar to the algorithm in [ 4 , 54 ] , our algorithm can be used for a wide range of classes of transformations. Specifically, given two curves \pi and \sigma of total complexity n and a threshold \delta\geq 0 , we want to determine whether there is a transformation \tau from a given class of transformations, such that the Fréchet distance between \pi and \tau(\sigma) is at most \delta . Our algorithm improves the running time for translations in two dimensions from \mathcal{O}(n^{8}) to \tilde{\mathcal{O}}(n^{7+\frac{1}{3}}) . More generally, we improve the running time for the various classes of transformations (and dimensions) given by Wenk [ 4 ] by roughly a factor of n^{2/3} . For example, for rotations or scalings in \mathbb{R}^{2} , our algorithm runs in \tilde{\mathcal{O}}(n^{4+\frac{1}{3}}) time and for affine transformations in d dimensions in \tilde{\mathcal{O}}(n^{3(d^{2}+d)+\frac{1}{3}}) time. We first present our approach for the special case of translations in two dimensions. Then we generalize our approach to other transformations and higher dimensions. Similarly to the approach in [ 4 ] , we compute an arrangement in the space of transformations, which in the case of 2D translations has complexity \mathcal{O}(n^{6}) . In [ 4 ] , the Fréchet distance is computed for every vertex of this arrangement in \mathcal{O}(n^{2}) time per vertex by using the free space diagram , which results in an overall running time of \mathcal{O}(n^{8}) . In our approach, we instead traverse the arrangement, making use of the fact that the free space diagram for adjacent faces in the arrangement is similar. The challenge with using this approach is that it requires a data structure for dynamic directed graph reachability. This is a challenging problem on its own that to the best of our knowledge mostly saw progress on planar graphs [ 31 , 44 , 48 ] or more specifically grid graphs [ 7 , 14 ] . In [ 14 ] , a data structure with efficient updates and queries for reachability in a dynamic directed grid graph is presented. However, while the discrete Fréchet distance naturally reduces to a reachability problem on such a grid, this is not the case for the (continuous) Fréchet distance. An open question is whether there is a dynamic graph reachability data structure more suitable for the case of the continuous Fréchet distance under transformations. We note that in an independent work, progress was made on the one-dimensional Fréchet distance under translation or scaling [ 9 ] . In this work, the authors present an