Computing the Discrete Fréchet Distance in Subquadratic Time

Details Computing the Discrete Fréchet Distance in Subquadratic Time Computing the Discrete Fréchet Distance in Subquadratic Time

2012-04-24

arxiv.org/abs/1204.5333v1

Computer Science

Computational Geometry

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computing the Discrete Fréchet Distance in Subquadratic Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing the Discrete Fréchet Distance in Subquadratic Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the Discrete Fréchet Distance in Subquadratic Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-519685