# Fr'echet Distance for Curves, Revisited

arXiv: https://arxiv.org/abs/1504.07685 · HTML: https://mlsanity.com/paper/1504.07685/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Apr 2015.

## Built on by (most cited first, 4 of 4)

- [Synthetic ECG Signal Generation Using Generative Neural Networks](https://mlsanity.com/paper/2112.03268/) (2021)
- [CANVAS: Commonsense-Aware Navigation System for Intuitive Human-Robot Interaction](https://mlsanity.com/paper/2410.01273/) (2024)
- [A comprehensive study of clustering a class of 2D shapes](https://mlsanity.com/paper/2111.06662/) (2021)
- [Infinite Gaze Generation for Videos with Autoregressive Diffusion](https://mlsanity.com/paper/2603.24938/) (2026)

## Abstract (arXiv)

renewcommandRerm I!hspace-0.025em R newcommandepsvarepsilon newcommandSetXmathsfX newcommandVorX[1]V pth#1 newcommandPolygonmathsfP newcommandSpaceoverlinemathsfm newcommandpth[2][!]#1left(#2right) We revisit the problem of computing Fr'echet distance between polygonal curves under L1, L2, and L_∞ norms, focusing on discrete Fr'echet distance, where only distance between vertices is considered. We develop efficient algorithms for two natural classes of curves. In particular, given two polygonal curves of n vertices each, a eps-approximation of their discrete Fr'echet distance can be computed in roughly O(nkappa3log n/eps3) time in three dimensions, if one of the curves is kappa-bounded. Previously, only a kappa-approximation algorithm was known. If both curves are the so-called backbone~curves, which are widely used to model protein backbones in molecular biology, we can eps-approximate their Fr'echet distance in near linear time in two dimensions, and in roughly O(n4/3log nm) time in three dimensions. In the second part, we propose a pseudo--output-sensitive algorithm for computing Fr'echet distance exactly. The complexity of the algorithm is a function of a quantity we call the emphbwnumber, which is quadratic in the worst case, but tends to be much smaller in practice.