Günter Rote:

Computing the Fréchet distance between piecewise smooth curves

  1. In: Abstracts of the 20th European Workshop on Computational Geometry, Seville, March 2004, pp. 147-150.
  2. 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.
  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: April 25, 2007.