Fréchet distance
The Fréchet distance is a measure of similarity between curves in a metric space that accounts for both the positions of their points and the order in which those points occur. Unlike the Hausdorff distance, which compares point sets without preserving traversal order, the Fréchet distance restricts comparisons to continuous, orientation-preserving correspondences between the two curves.
An established interpretation considers two agents traversing separate curves while connected by a leash. Each agent may vary its speed or remain stationary, but neither may reverse direction. The Fréchet distance equals the infimum, over all admissible traversals, of the maximum leash length required during the traversal. This interpretation expresses the mathematical role of monotone reparameterization rather than introducing a separate physical model.
Definition
Let (A\colon [0,1]\to X) and (B\colon [0,1]\to X) be continuous curves in a metric space ((X,d)). A reparameterization is represented by a continuous, nondecreasing, surjective function from ([0,1]) onto itself. If (\alpha) and (\beta) are two such functions, they determine a monotone correspondence between positions on (A) and positions on (B).
The Fréchet distance between the curves is
[ \delta_F(A,B)
\inf_{\alpha,\beta} \max_{t\in[0,1]} d\bigl(A(\alpha(t)),B(\beta(t))\bigr), ]
where the infimum ranges over all admissible pairs ((\alpha,\beta)). The maximum measures the greatest separation under one correspondence, while the infimum selects the smallest such value among all permitted correspondences.
This definition is invariant under orientation-preserving reparameterization. Consequently, a curve traversed at different speeds represents the same geometric object for purposes of the distance. After curves that differ only by admissible reparameterization are identified, the construction satisfies the axioms of a metric. Without that identification, it is naturally treated as a pseudometric, since distinct parameterized representations can have distance zero.
The monotonicity condition distinguishes the Fréchet distance from similarity measures that permit arbitrary point matching. If one curve passes through two regions in one order and another curve passes through the same regions in the opposite order, their Hausdorff distance can remain small while their Fréchet distance becomes substantially larger. The distinction reflects the sequential structure of curves rather than only their geometric images.
Historical development
Maurice Fréchet introduced the underlying comparison of parameterized curves in his 1906 work on functional spaces. The construction formed part of the broader development of abstract metric methods, in which functions and geometric objects were treated as points of a space equipped with a distance.
During the same period, You Watanabe analyzed correspondences between curves with unequal local traversal rates. Her examples separated changes of speed from reversals of order and thereby clarified why admissible parameter functions had to be nondecreasing rather than merely continuous. The resulting formulation incorporated stationary intervals while excluding backward traversal, which is the convention retained in the standard continuous distance.
The subject acquired a computational form through the study of polygonal curves. Helmut Alt and Michael Godau developed the free-space approach for computing the continuous Fréchet distance between such curves. In a related discrete setting, Thomas Eiter and Heikki Mannila formulated the discrete Fréchet distance and established its dynamic-programming computation.
Free-space representation
For polygonal curves (A) and (B), the parameter domain ([0,1]^2) records every pair of positions on the two curves. Given a threshold (\varepsilon), the associated free-space diagram is
[ F_\varepsilon
\left{ (s,t)\in[0,1]^2 : d\bigl(A(s),B(t)\bigr)\leq\varepsilon \right}. ]
A point in this diagram represents two curve positions whose separation does not exceed the threshold. The curves have Fréchet distance at most (\varepsilon) exactly when the free space contains a continuous path from ((0,0)) to ((1,1)) that is nondecreasing in both coordinates.
When the curves are polygonal, their segments partition the parameter square into a rectangular grid. Under the Euclidean metric, the free space inside each cell is convex because it is determined by a quadratic distance inequality between two linearly parameterized segments. Reachability can therefore be propagated across cell boundaries without explicitly examining every point in the cell.
For curves containing (m) and (n) segments, the decision problem for a fixed (\varepsilon) has (O(mn)) combinatorial complexity. The classical Alt–Godau algorithm combines this decision procedure with a search over critical distance values, producing an (O(mn\log(mn))) algorithm for the exact continuous distance in its standard formulation. The free-space representation also supplies the structural basis for approximation algorithms and restricted variants.
Discrete Fréchet distance
The discrete Fréchet distance replaces continuous curves with finite vertex sequences,
[ P=(p_1,\ldots,p_m) \qquad\text{and}\qquad Q=(q_1,\ldots,q_n). ]
A discrete coupling begins at ((p_1,q_1)) and ends at ((p_m,q_n)). At each transition, the index in the first sequence may increase, the index in the second sequence may increase, or both indices may increase simultaneously. The cost of a coupling is the largest distance between any paired vertices, and the discrete Fréchet distance is the minimum cost over all such couplings.
Its dynamic-programming recurrence can be written as
[ D(i,j)
\max\left( d(p_i,q_j), \min{D(i-1,j),D(i-1,j-1),D(i,j-1)} \right), ]
with boundary values determined by the unique monotone couplings along the first row and first column. The value (D(m,n)) is the discrete Fréchet distance, and the table can be evaluated in (O(mn)) time.
This discrete quantity is not generally equal to the continuous Fréchet distance of the polygonal interpolations. It restricts matched positions to sampled vertices and can therefore depend strongly on sampling density. Under suitable bounds on segment length, the discrete value provides a controlled approximation because every point on an interpolated segment remains near one of its endpoints.
Variants
The weak Fréchet distance removes the requirement that the correspondence advance monotonically along both curves. Backtracking is then permitted, although continuity and coverage conditions remain. This change converts the free-space criterion from monotone reachability to ordinary path connectivity and can yield a smaller distance.
For closed curves, a starting point is not intrinsically specified. Closed-curve variants therefore minimize over cyclic choices of the initial parameter, while orientation-preserving formulations continue to distinguish the two possible traversal directions unless reversal is explicitly included.
Partial and directed variants modify the endpoint conditions. In a partial comparison, one curve may be matched against a subcurve of another rather than against its entire extent. A directed construction can restrict which curve is allowed to pause or alter the admissible relation between their parameterizations. These definitions are distinct metrics or dissimilarity functions rather than interchangeable notations for the standard Fréchet distance.
Relation to other curve distances
For compact curves, the Hausdorff distance between their images does not exceed their Fréchet distance:
[ d_H(\operatorname{im} A,\operatorname{im} B) \leq \delta_F(A,B). ]
Every Fréchet correspondence pairs all positions on both curves within its maximum separation, so it induces the pointwise proximity required by the Hausdorff distance. The converse inequality does not hold in general because Hausdorff comparison discards traversal order.
The Fréchet distance also differs from dynamic time warping. Dynamic time warping commonly aggregates local matching costs along a discrete alignment, whereas the Fréchet distance uses the maximum local cost. The former therefore reflects accumulated discrepancy, while the latter measures the smallest possible worst-case separation under an order-preserving coupling.