Kevin Buchin, Maike Buchin, Christian Knauer, Günter Rote, and
How difficult is it to walk the dog?
In: Abstracts of the 23rd European Workshop on Computational
Graz, March 2007, pp. 170-173.
We study the complexity of computing the Fréchet distance (also
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
computation tree model allowing arithmetic operations and tests. Up to
only a O(n2) upper bound for the decision
The lower bound extends to variants of the Fréchet distance
the weak as well as the discrete Fréchet distance. For two
curves in one dimension, we give a linear-time algorithm to compute
weak Fréchet distance.
Last update: March 27, 2007.