Fréchet Distance

The Fréchet distance is a distance between curves that accounts for both the locations of their points and the ordering in which the points occur. Let and be continuous curves in a metric space . Their Fréchet distance is

(1)

where the infimum is over continuous nondecreasing surjections and . These maps allow the two curves to be traversed at independently varying speeds without reversing direction. Equivalently, the Fréchet distance is the shortest leash length that allows a person and a dog to traverse the two curves from their respective starting points to their endpoints without backtracking. This definition goes back to Fréchet (1906) and is the form used by Alt and Godau (1995).

The distance is unchanged when either curve is reparameterized by a continuous increasing bijection of its parameter interval. On parameterized curves it is a pseudometric; it becomes a metric on equivalence classes obtained by identifying curves at Fréchet distance 0.

The Hausdorff distance compares only the point sets traced by the curves, whereas the Fréchet distance also retains their ordering. In particular, . For example, the curves and on have the same image and therefore Hausdorff distance 0, but their Fréchet distance is 1 because they traverse the interval in opposite directions.

For finite point sequences and , a coupling is a sequence of ordered pairs of indices from to whose successive steps are , , or . The discrete Fréchet distance is

(2)

where the minimum is over all such couplings . If denotes the discrete Fréchet distance between the prefixes and , then for it satisfies

(3)

The boundary values are , with the first row and column obtained by successive maxima. Thus and the discrete distance can be computed in time (Eiter and Mannila 1994).