Computing Discrete Fréchet DistanceThomas Eiter and Heikki Mannila
Christian Doppler Labor für Expertensyteme
Technische Universität Wien
Paniglgasse 16, 1040 Wien
E-mail: eiter@vexpert.dbai.tuwien.ac.at

April 25, 1994

CD-TR 94/64

Computing Discrete Fréchet Distance∗
Thomas Eiter

Heikki Mannila

Information Systems Dept.
Technical University of Vienna

Dept. of Computer Science
University of Helsinki

Abstract
The Fréchet distance between two curves in a metric space is a measure of thesimilarity between the curves. We present a discrete variation of this measure.
It provides good approximations of the continuous measure and can be efficiently
computed using a simple algorithm. We also consider variants of discrete Fréchetdistance, and find an interesting connection to measuring distance between theories.

keywords: Fréchet distance, metrics, curves, polygonal curves

1

Introduction

Given two curves in a metric space, the Fréchet distance δF between them can be
defined intuitively as follows. A man is walking a dog on a leash: the man can moveon one curve, the dog on the other; both may vary their speed, but backtracking is notallowed. What is the length of the shortest leash that is sufficient for traversing bothcurves? The Fréchet 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 Hausdorff distance. This distance function was introduced
by Fréchet in 1906 [6].
A fundamental study on the computational properties of the Fréchet distance wasdone by Alt and Godau [1]. They give an algorithm that computes the exact Fréchetdistance between two polygonal curves in time O(pq log2 pq), where p and q are thenumber 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 Fréchet 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 Vienna, 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: eiter@vexpert.dbai.tuwien.ac.at, mannila@cs.helsinki.fi

1looking at all possible couplings between the end points of the line segments of thepolygonal curves.
We show that δdF provides good approximations to δF . Specifically, we show thatδdF is an upper bound for δF , and that the difference between these measures is boundedby the length of the longest edge of the polygonal curves. We also show that δdF canbe computed in O(pq) time using a very simple algorithm.
On the basis of these results, the following way of approximately computing theFréchet 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 Fréchet distance.
We also briefly address variants of the discrete Fréchet distance, and find an interesting relation to a measure of distance between logical theories.

2

Discrete Fréchet distance

Following [1], we define 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 : [a0 , b0 ] → V , their Fréchet distance is definedasδF (f, g) = inf max d(f (α(t)), g(β(t))),α,β t∈[0,1]where α (resp. β) is an arbitrary continuous nondecreasing function from [0, 1] onto
[a, b] (resp. [a0 , b0 ]).
In computing the Fréchet distance between arbitrary curves one typically approximates 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 affine, 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 thecoupling L is the length of the longest link in L, that is,||L|| = max d(uai , vbi ).
i=1,...,mGiven polygonal curves P and Q, their discrete Fréchet distance is defined 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 cancheck 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 defines 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 pointu ∈ σ(P ) let t(u) ∈ [0, 1] be the smallest value such that α(t(u)) = u, and for eachpoint v ∈ σ(Q) let s(v) ∈ [0, 1] be the smallest value such that β(s(v)) = v.
We construct a coupling R between P and Q iteratively. First add edge (u1 , v1 ) toR.
Assume then that R is already a coupling between the sequences (u1 , . . . , ui ) and(v1 , . . . , vj ). We extend R by one edge as follows. If j = q or t(ui+1 ) < s(vj+1 ), then
add the link (ui+1 , vj ). The endpoint vj of this link is the left endpoint of the line
segment in which the point β(t(ui+1 )) lies. Thus for the length of this link we have theinequalityd(ui+1 , vj ) ≤ d(α(t(ui+1 )), β(t(ui+1 ))) + D(Q).
(1)
If i = p or t(ui+1 ) > s(vj+1 ), then add the link (ui , vj+1 ). Again, the endpoint ui is theleft endpoint of the line segment in which the point α(s(vj+1 )) lies, and we have theinequalityd(ui , vj+1 ) ≤ d(α(s(vj+1 )), β(s(vj+1 ))) + D(Q).
(2)
Otherwise, we have t(ui+1 ) = s(vj+1 ), and we add the link (ui+1 , vj+1 ), whose length
is bounded byd(α(t(ui+1 ), β(t(ui+1 ))).
It is easy to see that the constructed sequence R is a coupling. The above inequalities 1
and 2 give us that||R|| ≤ max d(α(t), β(t)) + max{D(P ), D(Q)}.
t∈[0,1]3

Since α and β were arbitrary, we obtain||R|| ≤ δF (P, Q) + max{D(P ), D(Q)}. 2
Theorem 4 For any polygonal curves P and Q
δF (P, Q) ≤ δdF (P, Q) ≤ δF (P, Q) + max{D(P ), D(Q)}.
From this, we can regard the coupling measure δdF as a discrete version of the Fréchetdistance. More precisely, say that a polygonal curve Q is a refinement of the polygonal curve P , if σ(P ) = (u1 , . . . , un ) and for some i = 1, . . . , n we have σ(Q) =(u1 , . . . , ui , v, ui+1 , . . . , un ), and the point v is on the line segment between ui andui+1 . Then,
Proposition 5 Let P0 , P1 , . . . and Q0 , Q1 , . . . be sequences of polygonal curves such that
Pi+1 (resp. Qi+1 ) is a refinement of Pi (resp. Qi ) for all i ≥ 0 and limi→∞ D(Pi ) =limi→∞ D(Qi ) = 0. Then,lim δdF (Pi , Qi ) = δF (P0 , Q0 ).

i→∞

Proof. By Theorem 4. 2
In fact, from the results in [1] it can be seen that for any polygonal curves P =(u1 , . . . , up ) and Q = (v1 , . . . , vq ), there always exist sequences of refinements of P and
Q leading to curves P 0 and Q0 , respectively, that both contain at most p + q points andsatisfy δdF (P 0 , Q0 ) = δF (P, Q).

3

Computation

An advantage of the coupling measure is its efficient computability by dynamic programming, without need of complicated data structures. The algorithm dF in Table 1
can be coded easily; the following lemma on its output is straightforward.
Lemma 6 dF(P, Q) = δdF (P, Q) for any polygonal curves P and Q.
Thus, we obtain the following result.
Theorem 7 Let P : [0, n] → V and Q : [0, m] → V be polygonal curves. Denoteσ(P ) = (u1 , . . . , up ) and σ(Q) = (v1 , . . . , vq ). The measure δdF (P, Q) can be computedin O(pq) time.
Proof. By Lemma 6, dF(P, Q) computes δdF (P, Q). It is easy to see that the runtime
of dF(P, Q) is O(pq); hence the result. 2
We remark that an algorithm of Godau for deciding δF (P, Q) ≤ ? [7, 1] may be used toapproximate δF (P, Q) on a particular machine by doing a binary search over the range
r of reals that the computer normally handles. This amounts to an O(pq log r) timealgorithm for fixed range of reals, which works fine for practical purposes. However,
the algorithm is much more involved than the simple algorithm dF from above.
4

Function dF(P, Q): real;
input:
return:polygonal curves P = (u1 , . . . , up ) and Q = (v1 , . . . , vq ).
δdF (P, Q)

ca : array [1..p, 1..q] of real;function c(i, j): real;begin
if ca(i, j) > −1 then return ca(i, j)elsif i = 1 and j = 1 then ca(i, j) := d(u1 , v1 )elsif i > 1 and j = 1 then ca(i, j) := max{ c(i − 1, 1), d(ui , v1 ) }elsif i = 1 and j > 1 then ca(i, j) := max{ c(1, j − 1), d(u1 , vj ) }elsif i > 1 and j > 1 then ca(i, j) :=max{ min(c(i − 1, j), c(i − 1, j − 1), c(i, j − 1)), d(ui , vj ) }else ca(i, j) = ∞return ca(i, j);end; /* function c */begin
for i = 1 to p do for j = 1 to q do ca(i, j) := −1.0;
return c(p, q);
end.

Table 1: Algorithm computing the coupling measure

4

Variants of discrete Fréchet distance

A variant of discrete Fréchet distance is obtained if the length of a coupling L between
P and Q is measured by the sum of the links in L (denote this by ||L||s ), i.e.,||L||s =Xd(uai , vbi ).

i=1,...,mThe implied measure δsdF (P, Q) gives the minimum of the total distance of an orderpreserving correspondence between points of P and Q, such that each point of P
corresponds to at least one point of Q and vice versa. A dog-and-leash interpretationof this measure would be the minimum total length of leashes needed for men walking
their dogs, such that all points on the routes P and Q are occupied and leashes do not
cross over.
Clearly, δsdF (P, P ) = 0, δsdF (P, Q) = δsdF (Q, P ), and that δsdF (P, Q) = 0 implies
P = Q; the triangle inequality, however, fails in general. It is easy to see that δsdF
is computed by the variant of algorithm dF in Table 1 obtained by replacing “max”
operations with additions; hence, δsdF can be computed in time O(pq).
It is interesting to note a connection between measuring the distance of curves andthe distance of logical theories. If one gives up on order-preservation of couplings,
5then the measures defined as δdF and δsdF resemble two measures for distance between
logical theories. The motivation for studying such measures comes from the notion oftruthlikeness in philosophy of science [11] and from artificial intelligence, where the taskof quantifying the distance of theories is important for example for machine learningand theory approximation [10, 13, 12, 8, 3, 4]. Theories viewed as sets of models
naturally correspond to curves viewed as sets of points. Given a metric on the models,
the distance between the sets of models may be interpreted as a measure of similarity
between theories [11].
Let an unordered coupling between P and Q be any sequence U = (ua1 , vb1 ), (ua2 , vb2 ),. . . , (uam , vbm ) of distinct pairs from σ(P ) × σ(Q) such that every point in P (resp. Q)
occurs among the uai (resp. vbi ), and let ||U ||, ||U ||s be defined analogous as in the caseof ordered couplings. DefineuδdF(P, Q) = min{||U || | U is an unordered coupling between P and Q},uδsdF(P, Q) = min{||U ||s | U is an unordered coupling between P and Q}.
uBoth measures have been proposed for measuring theory distance. Notice that δdF
ucollapses with the Hausdorff distance. The measure δsdF describes the minimum costof a correspondence between the points of P and Q; it can be seen in the spirit of theunordered similarity measures in [2]. This measure, called link measure in the context
of [5], does not define a metric, since the triangle does not hold in general.
uIntuitively, the computation of δsdF
seems to be involved, and one might suspect NPu
hardness of this problem. Somewhat surprising, however, is that δsdF
can be computedin polynomial time by using graph matching techniques (cf. [9] for a background).
Given P , σ(P ) = (u1 , . . . , up ) and Q, σ(Q) = (v1 , . . . , vq ), define a complete bipartite graph G0 = (A ∪ B, E), where A = {a1 , . . . , ap } and B = {b1 , . . . , bq }, in which
each edge e = {ai , bj } has weight w(e) = d(ui , vj ). Let G1 be a zero-weight copy of G0 ,and let G be the graph obtained from G0 ∪ G1 by connecting each node from G to its
copy by weight equal to its nearest neighbor in G. Then, the following property of G
holds.

Theorem 8 Let P and Q be polygonal curves. The cost of a minimum perfect matchingu (P, Q).
in the graph G for P and Q is identical to δsdF
u
(A proof can be found in [5].) Consequently, δsdF
can be efficiently computed byapplying a minimum cost perfect matching algorithm, which is feasible in polynomial
time (cf. [9]).

5Conclusion

We have presented a discrete variant of the Fréchet distance between curves in a metricspace, and we described a simple and efficient algorithm for computing this measure.
Besides its own interest, discrete Fréchet distance may be used for approximately computing the Fréchet distance between two arbitrary curves, as an alternative to using
6the exact Fréchet distance between a polygonal approximation of the curves or an
approximation of this value.
Moreover, we found an interesting connection between distance of curves and logicaltheories. This connection suggests that distance measures for curves (sets of points)
may be fruitfully applied to logical theories (sets of models).
Acknowledgements We thank Michael Godau and Hannu Toivonen for useful comments on this paper.

References[1] H. Alt and M. Godau. Measuring the resemblance of polygonal curves. In Proc. 8th Annu.
ACM Sympos. Comput. Geom., pages 102–109, 1992.
[2] H. Alt, K. Mehlhorn, H. Wagener, and E. Welzl. Congruence, similarity and symmetriesof geometric objects. Discrete Comput. Geom., 3:237–256, 1988.
[3] M. Cadoli. Semantical and Computational Aspects of Horn Approximations. In Proceedings
IJCAI-93, pages 39–44, Chambery, France, August 1993.
[4] M. Cadoli and M. Schaerf. Tractable Reasoning via Approximation. Artificial Intelligence,
1993. To appear.
[5] T. Eiter and H. Mannila. Theory Distance and Similarity: Measures and Computation.
Technical Report CD-TR 94/60, CD-Laboratory for Expert Systems, TU Vienna, Austria,
February 1994.
[6] M. Fréchet. Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Mathematico
di Palermo, 22:1–74, 1906.
[7] M. Godau. A natural metric for curves – computing the distance for polygonal chains andapproximation algorithms. In Proc. 8th Sympos. Theor. Aspects of Comp. STACS, LNCS
vol. 480, pages 127–136, 1991.
[8] R. Greiner and D. Schuurmans. Learning Useful Horn Approximations. In Proceedings of
the Third International Conference on Knowledge Representation and Reasoning (KR-92),
pages 383–392, 1992.
[9] K. Mehlhorn. Graph Algorithms and NP-Completeness, volume 2 of Data Structures andAlgorithms. Springer, 1984.
[10] B. K. Natarajan. Machine Learning: A Theoretical Approach. Morgan Kaufmann, San
Mateo, CA, May 1991.
[11] I. Niiniluoto. Truthlikeness. D. Reidel Pub. Comp., Dordrecht, Holland, 1987.
[12] B. Selman and H. Kautz. Knowledge Compilation Using Horn Approximations. In Proceedings AAAI-91, pages 904–909, Anaheim, August 1991.
[13] S. Wrobel. On the Proper Definition of Minimality in Specialization and Theory Revision.
In P. B. Brazdil, editor, Machine Learning: ECML-93. European Conference on Machine
Learning, Lecture Notes in AI 667, pages 65–82. Springer-Verlag, 1993.

7