Computing the Discrete Fréchet Distance in Subquadratic Time

Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan +1

The Fréchet distance is a similarity measure between two curves $A$ and $B$: Informally, it is the minimum length of a leash required to connect a dog, constrained to be on $A$, an…