The Fréchet Distance Unleashed: Approximating a Dog with a Frog

The weak Fréchet distance allows morphings where the agents are allowed to go back and traverse portions of the curve visited previously (i.e., the morphing does not have to be $x/y$-monotone). Since the weak Fréchet distance allows considering more parameterizations, it is potentially smaller, and we have that ${𝖽}_{ℱ}^w(\pi ,\sigma )\le {𝖽}_{ℱ}(\pi ,\sigma )$, for any two curves $\pi ,\sigma$. Elegantly, Alt and Godau [1] showed the weak Fréchet distance can be reduced to computing the minimum spanning tree of an appropriate graph. Unfortunately, there does not seem to be a natural way to overcome this non-monotonicity (and thus get the “strong” version).

The complexity of these algorithms, together with sensitivity of the Fréchet distance to noise, lead to using “easier” related measures, such as the discrete version of the problem, and dynamic time-warping (discussed below). In the discrete version, you are given two sequences of points $p_1,\mathrm{\dots },p_n$, and $q_1,\mathrm{\dots },q_m$, and the purpose is for two “frogs” starting at $p_1$ and $q_1$, respectively, to jump through the points in the sequence until reaching $p_n,q_m$, respectively, while minimizing the maximum distance between the two frogs during this traversal. At each step, only one of the frogs can jump from its current location to the next point in its sequence (no jumping back). Computing the optimal distance under this measure can be done by dynamic-programming, similar to the standard approach to edit-distance. Indeed, the configuration space here is the grid $H=⟦n⟧\times ⟦m⟧$, where $⟦n⟧=\{1,\mathrm{\dots },n\}$.

To use the discrete version in the continuous case, one sprinkles enough points along both input curves, and then solves the discrete version of the problem. Beyond the error this introduces, to get a distance that is close to the standard Fréchet distance, one has to sample the two curves quite densely in some cases.

For the (monotone) discrete Fréchet distance the induced graph on the grid $H$ is a DAG, and the task of computing the Fréchet distance is to find a minimum bottleneck path from $(1,1)$ to $(n,m)$, where the weights are on the vertices. Here, the weight on the vertex $(i,j)$ is the distance $\Vert p_i-q_j\Vert$. In particular, a Fréchet morphing is an $x/y$-monotone path in $H$ from $(1,1)$ to $(n,m)$. The standard algorithm to do this traverses the grid, say, by increasing rows $i$, and in each row by increasing column $j$, such that the value at $(i,j)$ is the maximum of the length of the leash of this configuration, together with the minimum solution for $(i-1,j)$ and $(i,j-1)$. This algorithm leads to a straightforward, $O(nm)$ time algorithm for the discrete Fréchet distance. However, the morphing computed might be inferior, see Figure 1.2 for such a bad example.

For simplicity, assume that the pairwise distances between all pairs of points in the two sequences are unique. We would like to imagine that we have a retractable leash, that can become shorter at times, and the leash “resists” being longer than necessary. It is thus natural to ask for a morphing where the leash as short as possible at any point in time.

Informally, the optimal retractable Fréchet morphing between the two sequences includes the bottleneck configuration, realizing the Fréchet distance, in the middle of its path, and the two subpaths from the endpoints to this configuration have to be also recursively optimal. This is formally defined and described in the Full version of the paper [14]. This concept was introduced by Buchin et al. [6]. Interestingly, they show that the discrete version can be computed in $O(nm)$ time, but unfortunately, the algorithm is quite complicated. They also show that the continuous retractable Fréchet can be computed in $O(n^3\log n)$ time.

Buchin et al. [6] refers to this Fréchet distance as locally correct, but we prefer the retractable labeling. The term “retractable Fréchet” was used by Buchin et al. [7], but in a different (and not formally defined) context than ours.

One way to get less sensitivity for noise is to compute the total area “swept” by the leash as the walk is being performed. In the discrete case, we simply add up the lengths of the leashes during the configurations in the walk. There is also work on extending this to the continuous setting [15, 2]. For the continuous case this intuitively boils down to computing (or approximating) an integral along the morphing. See full version of the paper [14] for more details.

Because of the continuity and strict convexity of the elevation function, the function has a unique minimum on each edge of the free space diagram grid – geometrically, this is the minimum distance between a vertex of one curve, and an edge of the other curve (a vertex-edge event). We restrict our solution to enter and leave a cell only through these portals (which are easy to compute). The continuous configuration space now collapses to a discrete graph that is somewhat similar to the natural grid graph on $⟦n⟧\times ⟦m⟧$. Indeed, a grid cell has four portals on its boundary edges. Specifically, there are directed edges from the portal on the bottom edge, to the portal on the top and right edges of the cell. Similarly, there are edges from the portal on the left edge, to the portals lying on the top and right edges. As before, the values are on the portals, and our purpose is to compute the optimal bottleneck path in this grid-like graph. Examples of this graph are depicted in Figure 1.3, Figure 1.4 and Figure 1.5.

We can now run the retractable bottleneck shortest-path algorithm (i.e., the variant of Dijkstra described above) on this implicitly defined graph computing the vertices and edges of it, as they are being explored. For many natural inputs, this algorithm does not explore a large fraction of the configuration space, as it involves distances that are significantly larger than the maximum leash length needed. The algorithm seems to have near linear running time for many natural inputs. The VE-Fréchet morphing is the one induced by the computed path in this graph. Unfortunately, the VE-Fréchet morphing might allow the agents to move backwards on an edge, but importantly, the motion across a vertex is monotone. Namely, the VE-Fréchet is monotone for vertices, but not necessarily monotone on the edges. A vertex is thus a checkpoint that once passed, cannot be crossed back.

We denote the VE-Fréchet distance between two curves $\pi$ and $\sigma$ by ${𝖽}_{ℱ}^{ve}(\pi ,\sigma )$. Clearly, we have that ${𝖽}_{ℱ}^w(\pi ,\sigma )\le {𝖽}_{ℱ}^{ve}(\pi ,\sigma )\le {𝖽}_{ℱ}(\pi ,\sigma )$.

One can of course turn any morphing into a monotone one by staying put instead of moving back. This is appealing for VE-Fréchet, as the corresponding VE morphing $\mathrm{m}$, say between two curves $\pi$ and $\sigma$, never backtracks over vertices (only edges), so we already expect the error this introduces to be relatively small. Let ${\mathrm{m}}^{+}$ denote the monotone morphing resulting from this simple strategy. Observe that

In particular, if $\omega \left(\mathrm{m}\right)=\omega \left({\mathrm{m}}^{+}\right)$, then ${𝖽}_{ℱ}(\pi ,\sigma )$ is realized by ${\mathrm{m}}^{+}$, and we have computed the Fréchet distance between $\pi$ and $\sigma$.

A less aggressive approach is to introduce new vertices in the middle of the edges of $\pi$ and $\sigma$ as to enforce monotonicity. Indeed, clearly, if we refine both curves by repeatedly introducing vertices into them, the VE-Fréchet distance between the two curves converges to the Fréchet distance between the original curves, as introducing a vertex in the middle of an edge does not change the regular Fréchet distance, while preventing the VE-Fréchet morphing from backtracking over this point.

We refer to this process of adding vertices to the two curves as refinement. (See Figure 1.6.) In practice, in many cases, one or two rounds of (carefully implemented) refinement are enough to isolate the maximum leash in the morphing from the non-monotonicity, and followed by the above brute-force monotonization leads to the (practically) optimal Fréchet distance. Even for pathological examples, after a few more rounds of refinement, this process computes the almost-exact Fréchet distance. That is, the computed lower bound, which is the VE-Fréchet distance, is equal to the width of the computed monotone morphing, which is the Fréchet distance.

We demonstrate how one can convert our algorithm for computing VE-Fréchet to an algorithm that computes a variant of the CDTW distance, which we call the sweep distance. One can then use refinement to approximate the CDTW distance. One can also compute a lower bound on this quantity, and the two quantities converge. See the full version of the paper [14] for details.

We show how to preprocess a curve $\pi$ with $n$ vertices, in $O(n\log n)$ time, such that given a query $w$, one can quickly extract a simplification of $\overline{\pi }$ of $\pi$, such that ${𝖽}_{ℱ}(\pi ,\overline{\pi })\le w$. Importantly, the time to extract $\overline{\pi }$ is proportional to its size (i.e., the extraction is output sensitive). More importantly, in practice, this works quite well – the size of $\left|V\left(\overline{\pi }\right)\right|$ is reasonably close (by a constant factor) to the optimal approximation. Combined with greedy simplification, this yields a very good simplification result. See the full version of the paper [14] for details.