PDF《Computing Discrete Fr?》

Computing Discrete Fr? echet Distance Thomas Eiter and Heikki Mannila Christian Doppler Labor f¨ ur Expertensyteme Technische Universit¨ at Wien Paniglgasse 16,

1040 Wien E-mail: eiter@vexpert.

dbai.tuwien.ac.at April 25,

1994 CD-TR 94/64 Computing Discrete Fr? echet Distance? Thomas Eiter Information Systems Dept. Technical University of Vienna Heikki Mannila Dept. of Computer Science University of Helsinki Abstract The Fr? echet distance between two curves in a metric space is a measure of the similarity between the curves. We present a discrete variation of this measure. It provides good approximations of the continuous measure and can be e?ciently computed using a simple algorithm. We also consider variants of discrete Fr? echet distance, and ?nd an interesting connection to measuring distance between theories. keywords: Fr? echet distance, metrics, curves, polygonal curves

1 Introduction Given two curves in a metric space, the Fr? echet distance δF between them can be de?ned intuitively as follows. A man is walking a dog on a leash: the man can move on one curve, the dog on the other;

both may vary their speed, but backtracking is not allowed. What is the length of the shortest leash that is su?cient for traversing both curves? The Fr? echet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves. Therefore it is often better than the well-known Hausdor? distance. This distance function was introduced by Fr? echet in

1906 [6]. A fundamental study on the computational properties of the Fr? echet distance was done by Alt and Godau [1]. They give an algorithm that computes the exact Fr? echet distance between two polygonal curves in time O(pq log2 pq), where p and q are the number of segments on the polygonal curves. The algorithm is fairly involved, as it uses the parametric search technique. In this paper we describe a discrete variation of the Fr? echet distance for polygonal curves. The variation is called the coupling distance δdF . It is based on the idea of ? Authors'

addresses: Thomas Eiter, Information Systems Department, Technical University of Vi- enna, Paniglgasse 16, A-1040 Vienna, Austria;

Heikki Mannila, Department of Computer Science, University of Helsinki, P.O. Box

26 (Teollisuuskatu 23), SF-00014 University of Helsinki, Finland. email: [email protected], [email protected]

1 looking at all possible couplings between the end points of the line segments of the polygonal curves. We show that δdF provides good approximations to δF . Speci?cally, we show that δdF is an upper bound for δF , and that the di?erence between these measures is bounded by the length of the longest edge of the polygonal curves. We also show that δdF can be computed in O(pq) time using a very simple algorithm. On the basis of these results, the following way of approximately computing the Fr? echet distance between two arbitrary curves suggests itself: First compute proper polygonal approximations to the curves and then compute their coupling distance, rather than computing their exact Fr? echet distance. We also brie?y address variants of the discrete Fr? echet distance, and ?nd an inter- esting relation to a measure of distance between logical theories.

2 Discrete Fr? echet distance Following [1], we de?ne a curve as a continuous mapping f : [a, b] → V , where a, b ∈ and a ≤ b and (V, d) is a metric space. Given two curves f : [a, b] → V and g : [a , b ] → V , their Fr? echet distance is de?ned as δF (f, g) = inf α,β max t∈[0,1] d(f(α(t)), g(β(t))), where α (resp. β) is an arbitrary continuous nondecreasing function from [0, 1] onto [a, b] (resp. [a , b ]). In computing the Fr? echet distance between arbitrary curves one typically approx- imates the curves by polygonal curves. A polygonal curve is a curve P : [0, n] → V , where n is a positive integer, such that for each i ∈ {0, 1,n ? 1}, the restriction of P to the interval [i, i + 1] is a?ne, that is P(i + λ) = (1 ? λ)P(i) + λP(i + 1). Let P : [0, n] → V be a polygonal curve. We denote the sequence (P(0), P(1) P(n)) of endpoints of the line segments of P by σ(P). Let P and Q be polygonal curves and σ(P) = (u1,up) and σ(Q) = (v1,vq) the corresponding sequences. A coupling L between P and Q is a sequence (ua1 , vb1 ), (ua2 , vb2 uam , vbm ) of distinct pairs from σ(P) * σ(Q) such that a1 = 1, b1 = 1, am = p, bm = q, and for all i = 1,q we have ai+1 = ai or ai+1 = ai + 1, and bi+1 = bi or bi+1 = bi. Thus, a coupling has to respect the order of the points in P and Q. The length ||L|| of the coupling L is the length of the longest link in L, that is, ||L|| = max i=1,...,m d(uai , vbi ). Given polygonal curves P and Q, their discrete Fr? echet distance is de?ned to be δdF (P, Q) = min{||L|| | L is a coupling between P and Q}.

2 It is immediate that δdF (P, P) = 0, δdF (P, Q) = δdF (Q, P);

furthermore, one can check that δdF (P, Q) =

0 implies P = Q and that δdF (P, Q) ≤ δdF (P, R) + δdF (R, Q). We thus have the following. Proposition

1 δdF de?nes a metric on the set of polygonal curves. The relationship of δdF to δF is captured by the following two lemmata, from which we immediately obtain the quality of approximation. Lemma

2 For all polygonal curves P and Q we have δF (P, Q) ≤ δdF (P, Q). Proof. A coupling with maximal edge r gives a way of walking around P and Q with leash at most r.

2 Let for any polygonal curve P = (u1,up) denote D(P) = maxi=2,...,p d(ui?1, ui). Lemma

3 Let P : [0, n] → V and Q : [0, m] → V be polygonal curves. Then, δdF (P, Q) ≤ δF (P, Q) + max{D(P), D(Q)}. Proof. Let α(t) (resp. β(t)) be a continuous nondecreasing function from [0, 1] to [0, n] (resp. [0, m]). Let σ(P) = (u1,up) and σ(Q) = (v1,vq). For each point u ∈ σ(P) let t(u) ∈ [0, 1] be the smallest value such that α(t(u)) = u, and for ea........