Hansdorff distance between convex polygons

When talking about distances, we usually mean the shortest : for instance, if a point X is said to be at distance D of a polygon P, we generally assume that D is the distance from X to the nearest point of P. The same logic applies for polygons : if two polygons A and B are at some distance from each other, we commonly understand that distance as the shortest one between any point of A and any point of B. Formally, this is called a minimin function, because the distance D between A and B is given by

D(A,B)=min {min{d(a,b)}}, where a is one element of set A and b is one element of set B

That definition of distance between polygons can become quite unsatisfactory for some applications. For example, as two pictures below:

the distance of two triangles in the picture above may be D1, and the distance of triangles in left is D2. It is clear that D1 and D2 is equal, however, the relationship between points in polygons above cannot be as same as in left polygons. So, we need a new method to describe two sets of points.

Named after Felix Hausdorff (1868-1942), Hausdorff distance is the « maximum distance of a set to the nearest point in the other set » [Rote91]. More formally, Hausdorff distance from set A to set B is a maximin function, defined as

h(A,B)=max{min{d(a,b)}}, where a is a element of set A and b is a element of set B (eq. 2)

It should be noted that Hausdorff distance is oriented (we could say asymmetric as well), which means that most of times h(A, B) is not equal to h(B, A). This general condition also holds for the example of fig. 3, as h(A, B) = d(a1, b1), while h(B, A) = d(b2, a1). This asymmetry is a property of maximin functions, while minimin functions are symmetric.A more general definition of Hausdorff distance would be :

H (A, B) = max { h (A, B), h (B, A) } (eq. 3)

which defines the Hausdorff distance between A and B, while eq. 2 applied to Hausdorff distance from A to B (also called directed Hausdorff distance). The two distances h(A, B) and h(B, A) are sometimes termed as forward and backward Hausdorff distances of A to B. Although the terminology is not stable yet among authors, eq. 3 is usually meant when talking about Hausdorff distance. Unless otherwise mentionned, from now on we will also refer to eq. 3 when saying "Hausdorff distance".

If sets A and B are made of lines or polygons instead of single points, then H(A, B) applies to all defining points of these lines or polygons, and not only to their vertices. The brute force algorithm could no longer be used for computing Hausdorff distance between such sets, as they involve an infinite number of points.

All data and Pictures obtained from "cgm.cs.mcgill.ca"