Fréchet distance

free-space-diagram

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 often described as the distance a dog and its owner would accumulate if they were walking along their separate paths (each represented by a curve) without backtracking, where the dog is allowed to control the speed it walks but is constrained by the length of the leash. This analogy highlights the essence of the Fréchet distance: it is the minimum length of a leash required so that both the dog and the owner can traverse their respective paths from start to finish, possibly at varying speeds but without backtracking.

Definition

Formally, the Fréchet distance between two curves is defined using the concept of reparameterizations. A reparameterization is a continuous, non-decreasing, surjective function from the unit interval [0,1] to itself. Given two curves represented by continuous functions \(A: [0,1] \rightarrow \mathbb{R}^n\) and \(B: [0,1] \rightarrow \mathbb{R}^n\), the Fréchet distance is the infimum over all reparameterizations \(\alpha\) and \(\beta\) of the maximum distance at corresponding points: \[d_F(A,B) = \inf_{\alpha,\beta} \max_{t \in [0,1]} \|A(\alpha(t)) - B(\beta(t))\|.\]

Applications

The Fréchet distance has applications in various fields such as computational geometry, computer graphics, and trajectory analysis. In computational geometry, it is used to compare geometric shapes. In computer graphics, it can be applied to compare and morph shapes. In trajectory analysis, it is useful for comparing the paths of moving objects, such as animals during migration or vehicles in traffic.

Computation

Computing the Fréchet distance is a challenging problem, especially for curves in higher dimensions. For polygonal curves, where the curves are piecewise linear, there exists an algorithm that computes the Fréchet distance in \(O(nm \log(nm))\) time, where \(n\) and \(m\) are the numbers of vertices on each curve. This algorithm relies on dynamic programming and the concept of free space diagrams.

Variants

Several variants of the Fréchet distance have been developed to address specific needs. The discrete Fréchet distance is a simplification that considers only the vertices of polygonal curves, making it easier to compute. The weak Fréchet distance relaxes the requirement for the paths to be traversed from start to finish, allowing for more flexibility in applications where such strict adherence to the paths' ordering is not necessary.

See Also

• Hausdorff distance
• Dynamic time warping
• Edit distance