## Günter Rote:

# Computing the Fréchet distance between piecewise smooth
curves

- In:
*Abstracts of the 20th European Workshop on Computational
Geometry,
Seville, March 2004, pp. 147-150.*
*Computational Geometry, Theory and Applications 37
(2007),
162-174.* (Special issue for the 20th European Workshop on
Computational
Geometry)doi:10.1016/j.comgeo.2005.01.004

### Abstract

We consider the Fréchet distance between two curves which are
given
as a sequence of *m*+*n* curved pieces. If these pieces are
sufficiently well-behaved, we can compute the Fréchet distance
in
*O*(*mn* log(*mn*)) time. The decision version of the
problem
can be
solved in *O*(*mn*) time.
Last update: April 25, 2007.