Fréchet distance

From Wiki.GIS.com

In mathematics, the Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves. It is named after Maurice Fréchet.

Contents 1 Intuitive definition 2 Formal definition 3 Variants 4 References 5 Further reading

[edit] Intuitive definition

The Fréchet distance between two curves is the minimum length of a leash required to connect a dog and its owner as they walk without backtracking along their respective curves from one endpoint to the other. The definition is symmetric with respect to the two curves. Imagine a dog walking along one curve and the dog's owner walking along the other curve, connected by a leash. Both walk continuously along their respective curve from the prescribed start point to the prescribed end point of the curve. Both may vary their speed, and even stop, at arbitrary positions and for arbitrarily long. However, neither can backtrack. The Fréchet distance between the two curves is the length of the shortest leash that is sufficient for traversing both curves in this manner.

[edit] Formal definition

Let S be a metric space. A curve A in S is a continuous map from the unit interval into S, i.e., . A reparameterization α of [0,1] is a continuous, non-decreasing, surjection .

Let A and B be two given curves in S. Then, the Fréchet distance between A and B is defined as the infimum over all reparameterizations α and β of [0,1] of the maximum over all of the distance in S between A(α(t)) and B(β(t)). In mathematical notation, the Fréchet distance F(A,B) is

where d is the distance function of S.

Informally, we can think of the parameter t as "time". Then, A(α(t)) is the position of the dog and B(β(t)) is the position of the dog's owner at time t (or vice versa). The length of the leash between them at time t is the distance between A(α(t)) and B(β(t)). Taking the infimum over all possible reparametrizations of [0,1] corresponds to choosing the walk along the given paths where the maximum leash length is minimized. The restriction that α and β be non-decreasing means that neither the dog nor its owner can backtrack.

The Fréchet metric takes into account the flow of the two curves because the pairs of points whose distance contributes to the Fréchet distance sweep continuously along their respective curves. This makes the Fréchet distance a better measure of similarity for curves than alternatives, such as the Hausdorff distance, for arbitrary point sets. It is possible for two curves to have small Hausdorff distance but large Fréchet distance.

The Fréchet distance and its variants find application in several problems, from morphing^[1] and handwriting recognition^[2] to protein structure alignment^[3]. Alt and Godau^[4] were the first to describe a polynomial-time algorithm to compute the Fréchet distance between two polygonal curves in Euclidean space.

[edit] Variants

The weak Fréchet distance is a variant of the classical Fréchet distance without the requirement that the endpoints move monotonically along their respective curves — the dog and its owner are allowed to backtrack to keep the leash between them short. Alt and Godau^[4] describe a simpler algorithm to compute the weak Fréchet distance between polygonal curves.

The discrete Fréchet distance, also called the coupling distance, is an approximation of the Fréchet metric for polygonal curves, defined by Eiter and Mannila^[5]. The discrete Fréchet distance considers only positions of the leash where its endpoints are located at vertices of the two polygonal curves and never in the interior of an edge. This special structure allows the discrete Fréchet distance to be computed in polynomial time by an easy dynamic programming algorithm.

When the two curves are embedded in a metric space other than Euclidean space, such as a polyhedral terrain or some Euclidean space with obstacles, the distance between two points on the curves is most naturally defined as the length of the shortest path between them. The leash is required to be a geodesic joining its endpoints. The resulting metric between curves is called the geodesic Fréchet distance^[6][1][7]. Cook and Wenk^[6] describe a polynomial-time algorithm to compute the geodesic Fréchet distance between two polygonal curves in a simple polygon.

If we further require that the leash must move continuously in the ambient metric space, then we obtain the notion of the homotopic Fréchet distance^[8] between two curves. The leash cannot switch discontinuously from one position to another — in particular, the leash cannot jump over obstacles, and can sweep over a mountain on a terrain only if it is long enough. The motion of the leash describes a homotopy between the two curves. Chambers et al.^[8] describe a polynomial-time algorithm to compute the homotopic Fréchet distance between polygonal curves in the Euclidean plane with obstacles.

[edit] References

[edit] Further reading

• Fréchet distance for curves, revisited. Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk. In Proc. 14th European Symp. Algorithms, volume 4168 of Lect. Notes Comput. Sci., pages 52–63, Springer-Verlag, 2006.

• Semi-computability of the Fréchet distance between surfaces. Helmut Alt and Maike Buchin. In Proc. 21st European Workshop on Computational Geometry, pages 45–48, March 2005.

Please help improve this article or section by expanding it. Further information might be found on the talk page. (May 2009)