On Computing the (Exact) Fréchet Distance with a Frog

Computing the value of the Fréchet distance is considerably more intricate. The continuous distance is realised by one of three types of events (see Figure 1). Vertex events correspond to distances between pairs of vertices in $\pi \times \sigma$; edge events correspond to distances between a vertex of one curve and an edge of the other; and monotonicity events correspond to triples $(e,s,s^{\prime })$, where $e$ is an edge of one curve, $s,s^{\prime }$ are vertices of the other curve, and the corresponding distance value is realised by the point on $e$ minimising the maximum distance to $s$ and $s^{\prime }$. The discrete distance ${𝔻}_F(\pi ,\sigma )$ is always realised by a vertex event. As there are $O(nm)$ such events one may therefore compute all distances, sort them, and apply the decision procedure, yielding an $O(nm\log nm)$ algorithm (or $O(nm)$ with a simple dynamic program). This version is also easy to make exact, as one can simply square the vertex-weights to maintain rational input. For the continuous setting, monotonicity events introduce two significant difficulties:

• $\mathrm{■}$

  There are $O(n^3+m^3)$ such events, so no quadratic-time algorithm can enumerate them.

• $\mathrm{■}$

  Edge and monotonicity events involve equations that contain several square root monomials. They therefore offer no straightforward way to avoid numerical imprecision, even if the input is integral. This causes problems, not only for computing the distance value, but even for computing the correct combinatorial traversal that realises the Fréchet distance.

An exact decision procedure for the continuous variant was provided by [10], who use exact geometric predicates to test ${𝒟}_F(\pi ,\sigma )\le \mathrm{\Delta }$ in $O(nm)$ time. Their implementation allows an approximation of ${𝒟}_F(\pi ,\sigma )$ to $b$ bits precision via binary search in $O(nm(\log nm+\log b))$ time, but it does not compute the exact value.

[26] recently proposed a different approach. Given $(\pi ,\sigma )$ they construct what they call the VE-graph whose vertices correspond to all vertex and edge events. In this graph, there is an edge between two vertices if they share a cell and either the edge is monotone, or the events lie on an edge of the same curve (see Figure 2). The vertices are weighted by the event distance, and the shortest path from $(1,1)$ to $(n,m)$ in this graph corresponds to a (non-monotone) person-dog traversal $\gamma$. If $\gamma$ happens to be $xy$-monotone, its continuous counterpart realises the Fréchet distance. Otherwise, non-monotonicities certify that the Fréchet distance is realised by a monotonicity event. Instead of computing monotonicity events, their algorithm bisects each edge of $\pi$ and $\sigma$ where $\gamma$ is non-monotone in the corresponding row or column. This creates higher-complexity curves $({\pi }^{\prime },{\sigma }^{\prime })$ on which they recurse. They call this refinement, and its recursive application yields increasingly complex curves whose vertex and edge events approach the continuous Fréchet distance ${𝒟}_F(\pi ,\sigma )$. In the limit, this procedure converges to introducing the necessary monotonicity events and thereby computes the continuous Fréchet distance through discrete shortest paths.

Their second contribution is a clever simplification technique that is agnostic to how the Fréchet distance between curves is computed. They show how to simplify two input curves $(\pi ,\sigma )$ into lower-complexity curves $(\overline{\pi },\overline{\sigma })$ such that ${𝒟}_F(\pi ,\sigma )={𝒟}_F(\overline{\pi },\overline{\sigma })$. The procedure is iterative: they first compute simplified curves $(\overline{\pi },\overline{\sigma })$ and evaluate ${𝒟}_F(\overline{\pi },\overline{\sigma })$ using any method. This yields a person-dog traversal, from which they generate a witness certifying whether ${𝒟}_F(\overline{\pi },\overline{\sigma })={𝒟}_F(\pi ,\sigma )$ holds. If not, the curves are partially un-simplified, reintroducing complexity until the criterion is satisfied. Based on our observations, this simplification step is likely the main source of the speedy performance of their implementation.

The Fréchet distance has many well-known applications, in particular in the analysis and visualisation of movement data [11, 15, 29, 37], and has enjoyed continued interest in many different settings [18, 17, 7, 23, 2, 19, 1]. It is a versatile measure used across a wide range of domains, including handwriting [33], coastlines [30], geographic outlines [21], trajectories of vehicles, animals, and sports players [32, 34, 9, 15], air traffic [8], and protein structures [28]. These typically provide their own Fréchet distance implementations. A recent and particularly active domain is trajectory clustering, where the task is to group (sub)curves into clusters such that each cluster has low pairwise Fréchet distance. Several approaches adopt this principle, including the subtrajectory clustering algorithm of [3], the map construction and clustering algorithms [11, 12], the clustering method of [13] (implemented in the MOVETK library [24]), the clustering algorithm of [16], and the clustering of [35]. In the vast majority of these examples, the implementation computes the discrete Fréchet distance, as this is considerably easier to evaluate in practice.

Two of these approaches [11, 12] compute the semi-weak Fréchet distance, in which the person and the dog are not required to be monotone within an edge. This variant corresponds to the edge-monotone minimum-cost traversal computed from [26] before their curve refinement procedure is applied. These examples illustrate the need for efficient and adaptable Fréchet distance implementations, and highlight why the refinement-based approach of [26] is appealing: it suggests the possibility of computing the exact continuous Fréchet distance through a discrete traversal mechanism that is compatible with existing algorithmic paradigms and interfaces.

We re-examine the frog-based framework of [26], as we improve three aspects of their contribution.

We find the overarching method conceptually very interesting (and even elegant), however, their algorithm does not compute the exact Fréchet distance. They state that “as the calculation of the optimal Fréchet distance involves distances, impreciseness is unavoidable”. This is not necessarily true as there exist exact-evaluation predicates. In theory, one can even assume a real RAM. Their current approach would remain imprecise under such assumptions:

1. 1.

   Their implementation inherently uses floating-point arithmetic and thus imprecision.

2. 2.

   However, even with exact real-valued arithmetic, their edge bisection does not introduce the monotonicity events that realise the exact Fréchet distance. This refinement converges to the correct value only in the limit, with no bound on the number of required iterations.

Their lossless simplification step is theoretically sound and would yield the exact Fréchet distance under real-valued arithmetic. However, the procedure is somewhat crude: to ensure that the Fréchet distance remains unchanged after simplification, they impose overly conservative constraints on how the curves may be simplified. The original paper briefly acknowledges the possibility of an exact algorithm, but quickly states that “from implementation point of view such a modification seems pointless, and we did not pursue it any further”. Our motivation is to understand to what extent this framework can be made exact and efficient, and to provide the required components to do so.

1. 1.

   We explain in detail how to unpack square-root expressions for exact evaluation. This is non-trivial, particularly for monotonicity events and curve simplifications where several square-root terms must be handled simultaneously.

2. 2.

   We replace their heuristic refinement procedure with a new output-sensitive algorithm that generates the required monotonicity events on demand. As a consequence, we obtain provable polynomial-time convergence, even under real-valued computations.

3. 3.

   We strengthen the lossless simplification technique. Whilst the method from [26] works as a black-box given any Fréchet computation algorithm that outputs a traversal, we note that this frog-based paradigm allows for a tighter algorithm and analysis. This leads to an alternative and new algorithm for lossless simplification under the frog-based method.

We provide an open-source C++ implementation of our adapted algorithm with our exact arithmetic and monotonicity event-generation. This thereby is the first exact implementation. We experientially compare our solution to the one provided in [26]. Unsurprisingly, our median running times increase due to exact computation. Our exact-value representations simply do not allow for vectorisation, which comes at performance cost. Somewhat unexpectedly, the worst-case running time drastically improves. We can show instances where the recursive refinement encounters its worst-case behaviour and terminates with an approximation only after many refinement steps. For some data sets, the worst-case behaviour is such that even our average time is an improvement.

Our final contribution is the most significant. The original publication [26] claims that their running times are significantly faster than previous Fréchet computations. Across all our data sets, we observe a substantially different performance profile. In particular, the highly-optimised implementation of Bringmann, Künnemann, and Nusser BKN [10] dominates all frog-based implementations in performance (e.g., Figure 3). As a consequence of our discovery, the authors of [26] posted on their ArXiV version an errata explaining that their experimental setup was flawed.

At first sight, our empirical analysis may appear unfavourable to our contribution, as it shows that on many practical instances the performance of this new frog-based approach is surpassed by classical techniques. However, we argue for our significance: we provide the first exact Fréchet distance implementation. Moreover, the empirical analysis reported at SoCG’25 [26] claimed strong practical performance over [10]. Our broader evaluation provides a necessary complementary picture, contradicting this claim. We view this contrast as valuable to our community: it clarifies that this technique is valuable, but also clearly shows the limits of its use. Ultimately, we argue that the frog-based technique of [26] is of genuine theoretical interest, as it can be augmented to compute the exact Fréchet distance in a unique manner with provable guarantees. At the same time, its practical use is debatable.

We can decide whether ${𝒟}_F(\pi ,\sigma )\le \mathrm{\Delta }$ as follows. The area $\{(a,b)\in [1,n]\times [1,m]\mid d(\pi (a),\sigma (b))\le \mathrm{\Delta }\}$ is the free space. Via DFS over the free space we decide in $O(nm)$ time whether the free space contains a monotone curve from $(1,1)$ to $(n,m)$, i.e., ${𝒟}_F(\pi ,\sigma )\le \mathrm{\Delta }$ [5].

The Fréchet distance is realised by one of three types of events:

• $\mathrm{■}$

  Vertex events: distances between pairs of vertices in $\pi \times \sigma$.

• $\mathrm{■}$

  Edge events: distances between a vertex of one curve and an edge of the other.

• $\mathrm{■}$

  Monotonicity events: triples $(e,s,s^{\prime })$ where $e$ is an edge of one curve and $s,s^{\prime }$ are vertices of the other, corresponding to minimising the maximum distance to $s$ and $s^{\prime }$.

A naive algorithm enumerates all events in $O(n{m}^2+m{n}^2)$ time, sorts them, and performs a binary search with the decision algorithm to obtain ${𝒟}_F(\pi ,\sigma )$. [5] observed that many monotonicity events are irrelevant and achieved an $O(nm\log nm)$-time exact algorithm. [25] gave a considerably simpler approach: as $\mathrm{\Delta }$ increases, connected components of the free space merge, and a critical value is the smallest $\mathrm{\Delta }$ at which a new merge occurs. Each cell has one connected component, implying $O(nm)$ critical values. By comparing adjacent cells, all critical values can be generated in $O(nm\log nm)$ time. The fastest known algorithm is by [14], running in $O\left(n^2\sqrt{\log n}{(\log \log n)}^{3/2}\right)$ time.

For curves $(\pi ,\sigma )$ and a minimum-cost traversal $\gamma =\{\gamma (t)\mid t\in [0,1]\}$, define $\mathrm{cost}(\gamma ):={\max }_{(a,b)\in \gamma }d(\pi (a),\sigma (b)).$ Let $(a,b)\in \gamma$ be a point that attains this maximum. Then $\gamma$ decomposes into two open curves: ${\gamma }_1$ from $(1,1)$ to $(a,b)$ and ${\gamma }_2$ from $(a,b)$ to $(n,m)$. [26] call $\gamma$ retractable if ${\gamma }_1$ and ${\gamma }_2$ are minimum-cost monotone curves for their respective subcurves, and if ${\gamma }_1$ and ${\gamma }_2$ are themselves retractable (Figure 4). Computing the Fréchet distance using an adaption of Dijkstra yields a retractable traversal.

Given $LB(\overline{\pi },\overline{\sigma })$ and ${\gamma }^{\ast }(t)$, each curve vertex $v$ receives a slack $\text{slack}(v):=LB(\overline{\pi },\overline{\sigma })-g_v$, where $g_v$ is the maximum leash length attained at $v$ along ${\gamma }^{\ast }(t)$ (Figure 7). Negative slack marks $v$ as a bottleneck. Each vertex $p$ of $\overline{\pi }$ or $\overline{\sigma }$ inherits the minimum slack of all original vertices between $p$ and the next vertex. Slack is then heuristically propagated: every vertex adopts the minimum slack among its eight closest neighbours along $\overline{\pi }$ or $\overline{\sigma }$. The slack of an edge is the minimum slack of its endpoints. They then perform the following:

while there exists a negative-slack edge $e$ on $\overline{\pi }$ (resp. $\overline{\sigma }$), and the edge $e$ is not an edge of $\pi$ (resp. $\sigma$), un-simplify the edge $e$ (reintroducing missing vertices).

By construction of slack, its propagation, and (1), the process ends with ${𝒟}_F(\pi ,\sigma )={𝒟}_F(\overline{\pi },\overline{\sigma })$.

In the full version, we observe that the above technique, while elegant, is overly conservative and somewhat coarse [20]. We refine it in two ways.

(i) Tighter bounds. Their lower bound uses the global maximum leash length $M$ between $(\overline{\pi },\overline{\sigma })$, minus the global maxima $A$ and $B$ between $(\pi ,\overline{\pi })$ and $(\sigma ,\overline{\sigma })$, respectively. When $M$, $A$ and $B$ are realised at unrelated parts of the traversal (see Figure 7), this yields an unnecessarily small value $LB(\overline{\pi },\overline{\sigma })=M-A-B$. This in turn causes more vertices than needed to trigger unsimplification. Using the frog-based framework, we obtain a sharper bound (Figure 8). For each edge of $\overline{\pi }$ we compute the maximum leash length between that edge and $\pi$, and assign this as a negative weight. In the VE-graph, the eddys on this edge add this negative weight to their own weight. The min-cost path in this reweighted graph yields a lower bound for ${𝒟}_F(\pi ,\sigma )$ by the same triangle-inequality argument as in [26], but now based on local rather than global maxima. For many instances, this increases the lower bound and therefore the slack of vertices – causing our algorithm to unsimplify fewer edges.

(ii) A tighter slack propagation rule. Their propagation step takes the minimum slack over each block of eight consecutive vertices. This removes any edge cases for applying the slack, ensuring their correctness. However, this method is also rather crude and causes unnecessary unsimplification. We tighten this step by propagating slack along at most two edges per vertex, avoiding this coarse eight-neighbour spread.

The analysis in [26] uses three animal-tracking data sets: Geolife, Birds, and Pigeons. These trajectories are goal-oriented. Their implementation benefits from this in one major way compared to [10]: as a simplification is applied, this greatly reduces complexity. Consequently, they operate on significantly smaller effective input.

The lossless simplification of [26] applies to any Fréchet algorithm, including [10]. We could enable a direct comparison by applying it to [10]. Yet, we deliberately refrain from doing so: the simplification incurs overhead, and [10] is so fast that this may actually slow it down. Despite not using simplifications, our experiments will show that [10] dominates the frog-based approaches, removing the need to improve it further. All experiments are single-threaded and executed on an AMD Ryzen 5 7600X (4.7 GHz) with 96 GB RAM.

Our real-world data sets are summarised in Table 1. The first two (Geolife, Pigeons) are from [26]. We additionally include Athens, Chicago, and Berlin GPS traffic data sets, widely used in Fréchet benchmarks [4, 11, 27, 36]. We include the Drifter data set of [16], containing drifting-buoy trajectories. We add the UnID data set from [31] which is a traffic dataset captured on German highways. Except for Drifter, these sets are goal-oriented with minimal backtracking; lossless simplification therefore removes relatively many vertices, which favours the frog-based approaches. Finally, we include a set OV¹¹1Obtained via personal communication with one author from [10], available with our source code of difficult synthetic pairs of curves that are derived from Orthogonal Vectors instances [10].

The Geolife data set alone induces over $170,000,000$ pairs of curves, so we cannot possibly compute the Fréchet distance between all pairs of curves. We follow [26] and subsample. In our case, we compare all $45,000$ pairs among a subselection of $300$ curves from the Geolife and Pigeons data sets. We further augment the analysis by comparing all curves from the Athens data set and from the adversarial OV data set. To broaden our evaluation, we also include the remaining real-world data sets, where, due to time constraints, we subsample curves and compare all pairs among them. The experiments are primarily bottlenecked by the Unleashed implementation²²2A time limit of $5$ minutes was hit multiple times, and the full evaluation requires several days to complete. Our results indicate no substantial qualitative differences between sampling $100\times 100$ or $300\times 300$ curves from the same data.

Our primary evaluation metric is running time (including file-reading time). For exactness, our approach is the most accurate if the input coordinates fit within a $32$-bit integer, followed closely by BKN; Table 2 briefly reports accuracies for the data sets satisfying this condition. We could compare across all data by truncating all input to 32-bit coordinates, but we refrain from doing so since BKN can handle this data natively (albeit inexact).