Fréchet distance

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.

Intuitive definitionEdit

Imagine a person traversing a finite curved path while walking their dog on a leash, with the dog traversing a separate finite curved path. Each can vary their speed to keep slack in the leash, but neither can move backwards. The Fréchet distance between the two curves is the length of the shortest leash sufficient for both to traverse their separate paths from start to finish. Note that the definition is symmetric with respect to the two curves—the Frechet distance would be the same if the dog were walking its owner.

Formal definitionEdit

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

Let   and   be two given curves in  . Then, the Fréchet distance between   and   is defined as the infimum over all reparameterizations   and   of   of the maximum over all   of the distance in   between   and  . In mathematical notation, the Fréchet distance   is

 

where   is the distance function of  .

Informally, we can think of the parameter   as "time". Then,   is the position of the dog and   is the position of the dog's owner at time   (or vice versa). The length of the leash between them at time   is the distance between   and  . Taking the infimum over all possible reparametrizations of   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, based on the principle of parametric search. The running time of their algorithm is   for two polygonal curves with m and n segments.

The free-space diagramEdit

 
Free-space diagram of the red and the blue curve. In contrast to the definition in the text, which uses the parameter interval [0,1] for both curves, the curves are parameterized by arc length in this example.

An important tool for calculating the Fréchet distance of two curves is the free-space diagram, which was introduced by Alt and Godau.[4] The free-space diagram between two curves for a given distance threshold ε is a two-dimensional region in the parameter space that consist of all point pairs on the two curves at distance at most ε:

 

The Fréchet distance   is at most ε if and only if the free-space diagram   contains a path from the lower left corner to the upper right corner, which is monotone both in the horizontal and in the vertical direction.

As a distance between probability distributions (the FID score)Edit

In addition to measuring the distances between curves, the Fréchet distance can also be used to measure the difference between probability distributions. For two multivariate Gaussian distributions with means   and   and covariance matrices   and  , the Fréchet distance between these distributions is[5]

 .

This distance is the basis for the Fréchet inception distance (FID) that is used to compare images produced by a generative adversarial network with the real images that were used for training.

VariantsEdit

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, based on computing minimax paths in an associated grid graph.

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.[6] 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.[1][7][8] Cook and Wenk[7] 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[9] 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.[9] describe a polynomial-time algorithm to compute the homotopic Fréchet distance between polygonal curves in the Euclidean plane with obstacles.

ExamplesEdit

The Fréchet distance between two concentric circles of radius   and   respectively is   The longest leash is required when the owner stands still and the dog travels to the opposite side of the circle ( ), and the shortest leash when both owner and dog walk at a constant angular velocity around the circle ( ).

ReferencesEdit

  1. ^ a b Efrat, Alon; Guibas, Leonidas J.; Har-Peled, Sariel; Mitchell, Joseph S. B.; Murali, T. M. (2002), "New similarity measures between polylines with applications to morphing and polygon sweeping" (PDF), Discrete and Computational Geometry, 28 (4): 535–569, doi:10.1007/s00454-002-2886-1.
  2. ^ Sriraghavendra, R.; Karthik, K.; Bhattacharyya, Chiranjib (2007), "Fréchet distance based approach for searching online handwritten documents", Proc. 9th International Conference on Document Analysis and Recognition (ICDAR '07), pp. 461–465, doi:10.1109/ICDAR.2007.121.
  3. ^ Minghui, Jiang; Ying, Xu; Binhai, Zhu (2008), "Protein structure-structure alignment with discrete Fréchet distance" (PDF), Journal of Bioinformatics and Computational Biology, 6 (1): 51–64, doi:10.1142/S0219720008003278, PMID 18324745.
  4. ^ a b c Alt, Helmut; Godau, Michael (1995), "Computing the Fréchet distance between two polygonal curves" (PDF), International Journal of Computational Geometry and Applications, 5 (1–2): 75–91, doi:10.1142/S0218195995000064.
  5. ^ Dowson, D. C; Landau, B. V (1 September 1982). "The Fréchet distance between multivariate normal distributions". Journal of Multivariate Analysis. 12 (3): 450–455. doi:10.1016/0047-259X(82)90077-X. ISSN 0047-259X.
  6. ^ Eiter, Thomas; Mannila, Heikki (1994), Computing discrete Fréchet distance (PDF), Tech. Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria.
  7. ^ a b Cook, Atlas F., IV; Wenk, Carola (2008), Geodesic Fréchet distance with polygonal obstacles (PDF), Tech. Report CS-TR-2008-0010, University of Texas at San Antonio.
  8. ^ Maheshwari, Anil; Yi, Jiehua (2005), "On computing Fréchet distance of two paths on a convex polyhedron", Proc. 21st European Workshop on Computational Geometry (PDF), pp. 41–44.
  9. ^ a b Chambers, Erin Wolf; Colin de Verdière, Éric; Erickson, Jeff; Lazard, Sylvain; Lazarus, Francis; Thite, Shripad (2009), "Homotopic Fréchet distance between curves, or Walking your dog in the woods in polynomial time" (PDF), Computational Geometry: Theory and Applications, 43 (3): 295–311, doi:10.1016/j.comgeo.2009.02.008.

Further readingEdit