Math @ Duke

Publications [#303193] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Avraham, RB; Kaplan, H; Sharir, M, Computing the Discrete Fréchet Distance in Subquadratic Time,
Siam Journal on Computing, vol. 43 no. 2
(January, 2014),
pp. 429449 [1204.5333v1], [doi]
(last updated on 2018/10/21)
Abstract: The Fr\'echet distance is a similarity measure between two curves $A$ and
$B$: Informally, it is the minimum length of a leash required to connect a dog,
constrained to be on $A$, and its owner, constrained to be on $B$, as they walk
without backtracking along their respective curves from one endpoint to the
other. The advantage of this measure on other measures such as the Hausdorff
distance is that it takes into account the ordering of the points along the
curves.
The discrete Fr\'echet distance replaces the dog and its owner by a pair of
frogs that can only reside on $n$ and $m$ specific pebbles on the curves $A$
and $B$, respectively. These frogs hop from a pebble to the next without
backtracking. The discrete Fr\'echet distance can be computed by a rather
straightforward quadratic dynamic programming algorithm. However, despite a
considerable amount of work on this problem and its variations, there is no
subquadratic algorithm known, even for approximation versions of the problem.
In this paper we present a subquadratic algorithm for computing the discrete
Fr\'echet distance between two sequences of points in the plane, of respective
lengths $m\le n$. The algorithm runs in $O(\dfrac{mn\log\log n}{\log n})$ time
and uses $O(n+m)$ storage. Our approach uses the geometry of the problem in a
subtle way to encode legal positions of the frogs as states of a finite
automata.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

