# Fast Frechet Distance Between Curves With Long Edges

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

## Key facts

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

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

- [An Unsupervised Learning Method with Convolutional Auto-Encoder for Vessel Trajectory Similarity Computation](https://mlsanity.com/paper/2101.03169/) (2021)

## Abstract (arXiv)

Computing the Fr'echet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fr'echet distance computations become easier. Let P and Q be two polygonal curves in ℝd with n and m vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fr'echet distance between them: (1) a linear-time algorithm for deciding the Fr'echet distance between two curves, (2) an algorithm that computes the Fr'echet distance in O((n+m)log (n+m)) time, (3) a linear-time √d-approximation algorithm, and (4) a data structure that supports O(mlog2 n)-time decision queries, where m is the number of vertices of the query curve and n the number of vertices of the preprocessed curve.