# Computing the Fréchet distance between two polygonal curves

By Stéphane Pelletier

Note : This web page requires the plugin for Java 2 v1.4.1 Maurice Fréchet (1878-1973)

### 1.  Introduction

In object recognition applications, the objects of interest are often modelized in the system database by their shape, and thus, an important step of the recognition process consists generally to look for known shapes in an image. In many applications, two-dimensional shapes are given by the planar curves forming their boundaries. Consequently, a natural problem in shape comparison and recognition is to measure how much two given curves resemble each other. Naturally, the first question to be answered is what distance measure between curves should be used to reflect the intuitive notion of resemblance.

One possibility consists in approximating each curve by a set of points and then using the Hausdorff distance, which is defined as follows: (eq. 1)

where d is the underlying metric in the plane, for example the Euclidian distance, and A and B are the two sets of points describing the two curves to be compared. While the Hausdorff distance is an appropriate measure in many applications, the following figure shows an example where it is not. The two curves have a small Hausdorff distance, but do not look like each other at all. Figure 1: Problem with Hausdorff distance

The reason of this discrepancy is that the Hausdorff distance only takes into account the sets of points on both curves and does not reflect the course of the curves. However, the course of curves is important in many applications, for example in handwriting recognition. In order to overcome this problem, one can use the Fréchet distance, that was first defined by Maurice Fréchet (1878-1973).

### 2.  What is Fréchet distance ?

The Fréchet distance can be illustrated as follows : suppose a man is walking his dog and that he is constrained to walk on a curve and his dog on another curve. Both the man and the dog are allowed to control their speed independently, but are not allowed to go backwards. Then, the Fréchet distance of the curves is the minimal length of a leash that is necessary.

As performing mathematical operations on a curve of arbitrary shape turns out to be difficult in some cases, it is often useful to approximate a curve by a polygonal curve. A polygonal curve P:[0, N] is a continuous and piecewise linear curve made of N connected segments. Such a curve can be parametrized with a parameter a  such that P(a) refers to a given position on the curve, with P(0) refering to the first vertex of the polygonal curve and P(N) refering to its last vertex, as shown in the following figure. Figure 2: Parametrization of a polygonal curve

Now, suppose that the man of the previous example is constrained to walk on a polygonal curve P of length N and that his dog has to walk on a polygonal curve Q of length M. The position of the man and the dog on their respective curve can be modelized as a function of t by using two continuous and increasing function α(t) and β(t), where α(0) = 0, α(1) = N, β(0) = 0 and β(1) = M. The position of the man as a function of time is given by P(α(t)) and the position of the dog by Q(β(t)). While many functions α(t) and β(t) can be used, some of them will cause the distance between the dog and the man to be large at some instant, whereas other functions will not. Finding the Fréchet distance actually corresponds to find two parametrization functions α(t) and β(t) that minimize the maximum distance between the man and his dog.

The following applet illustrates the effect of α(t) and β(t) on the maximum distance. Select one of the two examples, click on the run button and observe how the cursors move along the curves. You will notice that the maximum distance between the two cursors is not the same for both examples.

Java applet

Mathematically, the Fréchet distance between two curves is defined as (eq. 2)

where α(t) and β(t) range over continuous and increasing functions with α(0) = 0, α(1) = N, β(0) = 0 and β(1) = M only.

This equation reads like: for every possible function α(t) and β(t), find the largest distance between the man and its dog as they walk along their respective path; finally, keep the smallest distance found among these maximum distances.

For simplicity, we'll take d(a,b) as the Euclidian distance between a and b.

### 3. Computing the Fréchet distance between two polygonal curves

#### 3.1 Decision problem

In a first time, let's consider an easier variant of the problem, namely the following decision problem:

Given: polygonal curves P and Q and some ε ≥ 0

Decide: whether δF(P,Q) ≤ ε

Throughout the rest of this tutorial, let P:[0,p] and Q:[0,q] be polygonal curves. Therefore, p and q are the number of edges of P and Q respectively. In order to solve the decision problem, let us first consider the case where p = q = 1, i.e. P and Q are just simple segments. We define (eq. 3)

that describes all pairs of points, one on P, one on Q, whose distance is at most ε. The following figure shows line segments P, Q, a distance ε > 0, and Fε being the white area within the unit square; subsequently called the free space. Figure 3: Free space of two segments

We can extend equation 3 to arbitrary polygonal curves P, Q, of length p, q respectively: (eq. 4)

The free space corresponding to the curves P and Q is the combination of the free spaces of all pairs containing one segment of P and one segment of Q. The following figure shows two polygonal curves and their corresponding free space for a given value of ε. Figure 4: Free space of two polygonal curves

The algorithm is based on the following straightforward observation:

For polygonal curves P and Q we have δF(P, Q) ≤ ε, exactly if there exists a curve within the corresponding Fε from (0, 0) to (p, q) which is monotone in both coordinates.

In the man-dog example, the monotonicity condition corresponds to the fact that none of them is allowed to go backwards. Figure 3 shows such a curve proving that for that example the Fréchet distance is lower than ε.

Now, let Fε(i, j) with 1 ≤ ip, 1 ≤ jq refer to the free cell corresponding to the segment P(i - 1) P(i) and the segment Q(i - 1)Q(i). What we are interested in at this point is to find the intersection of the free space with the contour of each Fε(i, j). If the free space intersects the edge of a cell, it means that it is possible to enter in that cell through this edge. As the free space of each unit cell is convex, it is an easy matter to determine if there is a monotone curve that goes from (0,0) to (p, q) by computing all the intersections of the free space with the contour of each cell. The following figure illustrates the values that must be calculated in order to identify the passages between neighboring cells. LFi,j refers to the left line segment bounding Fε(i, j) and BFi,j refers to the bottom line segment. Figure 5: Values that must be calculated

Furthermore, we define (eq. 5)

The following figure shows the difference between Fε and R ε. One can see that all the zones that were not reachable by a monotone curve in Fε have been removed in Rε. Hereafter, Rε will be referred to as the monotone free space. Figure 6: Monotone free space of two polygonal curves

Rε can easily be computed from Fε. We will use almost the same notation as in figure 5 above to designate the values that have to be calculated for the monotone free space. That is, LRi,j will refer to the left line segment bounding Rε(i, j) and BRi,j will refer to the bottom line segment.

#### 3.1.1 Algorithm for solving the decision problem

1. for each feasible pair (i, j) do compute LFi, j and BFi, j
2. for i := 1 to p do determine BRi, 1
3. for i := 1 to q do determine LR1, j
4. for i := 1 to p do
for j := 1 to q do
construct LRi+1, j and BRi, j+1 from LRi, j, BRi, j, LFi+1, j, BRi, j+1
5. answer yes if (p, q) LRp+1, q no otherwise.

#### 3.1.2 Complexity

The values of figure 5 can be calculated in constant time for each free space cell by using any algorithm that computes segment-circle intersections. Therefore, if polygonal curves P and Q respectively have p and q segments, then the previous algorithm decides in O(pq) time, whether δ F(P,Q) ≤ ε.

#### 3.2 Finding the Fréchet distance

Now, let us consider the problem of really computing the Fréchet distance. Assume that we start with ε = 0 and continuously increase ε. Then the free space becomes larger and larger and we want to determine the smallest ε such that it contains a monotone curve from (0,0) to (p,q). Observe that this can occur only in one of the following cases:

a) ε is minimal with (0,0) Fε and (p,q) Fε
b) ε is minimal with LFi, j or BFi,j becomes nonempty for some pair (i,j).
c) ε is minimal with ai,j = bk,j or ci,j = di,k for some i,j,k

Clearly, case a) states that δF(P,Q) must be greater or egal to the distance between the starting points of P and Q and also greater or egal to the distance between their ending points. Case b) corresponds to the opening of a new passage between two neighboring cells and case c) corresponds to the opening of a new vertical or horizontal passage within the diagram. The following figure illustrates case c) for a horizontal passage. Figure 7: Horizontal passage that opens

The following figure shows the geometric meaning of ε in cases a), b) and c). Figure 8: Geometric meaning of critical values

There are O(p2q + pq2) such critical values of ε, namely the distance between starting points and endpoints of P and Q (case a), the distances between vertices of one curve and edges of the other (case b), and the common distance of two vertices of one curve to the intersection point of their bisector with some edge of the other (case c). Each one of these values can be computed in O(1) time. So, we obtain the following algorithm for computing δF(P,Q).

#### 3.2.1 Algorithm for finding the Fréchet distance

• Determine all critical values of ε
• Sort them
• Do a binary search on the sorted sequence in each search step solving the decision problem, continuing with the half containing smaller critical values if it has a positive answer and with the half containing larger critical values otherwise.

#### 3.2.2 Complexity

We observe that the runtime is majorized by the one of step 2, which is O((p2q + q2p)log(pq)).

### 4. Applet

The following applet illustrates the algorithm. For simplicity reasons, the implemented algorithm doesn't calculate the critical values of ε that correspond to case c).

### Instructions for using the applet

• Enter polygonal curves P and Q by clicking in the left window. Use the Define P and Define Q buttons to specify which curve you are defining. The free space is calculated automatically as you define the polygonal curves and is displayed in the middle window.
• If you want to know the points on P and Q that correspond to a specific location in the free space, click at that location in the free space window (middle one). Two cursors will be placed on the curves in the left window at the corresponding points.
• Use the checkboxes on the right to toggle between the free space and the monotone free space.
• Use the slidebar to change the value of ε
• Click on the Critical Values button to generate the critical values of ε. The values will be listed in the window on the right and you can select them to see the corresponding free space.
• The Detail button can be used to calculate the critical values step by step. The geometric meaning of the critical values is also showed in the left window as they are calculated. The final value obtained for ε is the Fréchet distance.
• If the current value of ε is greater than the Fréchet distance, a monotone path from (0, 0) to (p, q) is displayed.

Java applet

### 5. References

1. H. Alt and M. Godau, Computing the Fréchet distance between two polygonal curves, Internat. J. Comput. Geom. Appl., 5:75-91, 1995
2. H. Alt, C. Knauer and C. Wenk, Matching polygonal curves with respect to the Fréchet distance", Proc. 18th Int. Symp. Theoretical Aspect of Computer Science (STACS):63-74, 2001, Dresden, Germany
3. H. Alt, C. Knauer and C. Wenk, Bounding the Fréchet distance by the Hausdorff distance", Proc. 17th European Workshop on Computational Geometry., 166-169, 2001, Berlin, Germany