Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, and Carola Wenk:

How difficult is it to walk the dog?

In: Abstracts of the 23rd European Workshop on Computational Geometry, Graz, March 2007, pp. 170-173.


We study the complexity of computing the Fréchet distance (also called dog-leash distance) between two polygonal curves with a total number of n vertices. For two polygonal curves in the plane we prove an Ω(n log n) lower bound for the decision problem in the algebraic computation tree model allowing arithmetic operations and tests. Up to now only a O(n2) upper bound for the decision problem was known.

The lower bound extends to variants of the Fréchet distance such as the weak as well as the discrete Fréchet distance. For two polygonal curves in one dimension, we give a linear-time algorithm to compute their weak Fréchet distance.

  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: March 27, 2007.