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.
Abstract
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.
Last update: March 27, 2007.