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.