Hausdorff Distance
Get Hausdorff Distance essential facts below. View Videos or join the Hausdorff Distance discussion. Add Hausdorff Distance to your PopFlock.com topic list for future reference or share this resource on social media.
Hausdorff Distance

In mathematics, the Hausdorff distance, or Hausdorff metric, also called Pompeiu-Hausdorff distance,[1][2] measures how far two subsets of a metric space are from each other. It turns the set of non-empty compact subsets of a metric space into a metric space in its own right. It is named after Felix Hausdorff and Dimitrie Pompeiu.

Informally, two sets are close in the Hausdorff distance if every point of either set is close to some point of the other set. The Hausdorff distance is the longest distance you can be forced to travel by an adversary who chooses a point in one of the two sets, from where you then must travel to the other set. In other words, it is the greatest of all the distances from a point in one set to the closest point in the other set.

It seems that this distance was first introduced by Hausdorff in his book Grundzüge der Mengenlehre, first published in 1914, although a very close relative appeared in the doctoral thesis of Maurice Fréchet in 1906, in his study of the space of all continuous curves from ${\displaystyle [0,1]\to \mathbb {R} ^{3}}$.

## Definition

Components of the calculation of the Hausdorff distance between the green line X and the blue line Y.

Let X and Y be two non-empty subsets of a metric space ${\displaystyle (M,d)}$. We define their Hausdorff distance ${\displaystyle d_{\mathrm {H} }(X,Y)}$ by

${\displaystyle d_{\mathrm {H} }(X,Y)=\max \left\{\,\sup _{x\in X}\inf _{y\in Y}d(x,y),\,\sup _{y\in Y}\inf _{x\in X}d(x,y)\,\right\},\!}$

where sup represents the supremum and inf the infimum.

Equivalently,

${\displaystyle d_{H}(X,Y)=\inf\{\varepsilon \geq 0\,;\ X\subseteq Y_{\varepsilon }{\text{ and }}Y\subseteq X_{\varepsilon }\},\quad }$[3]

where

${\displaystyle X_{\varepsilon }:=\bigcup _{x\in X}\{z\in M\,;\ d(z,x)\leq \varepsilon \},}$

that is, the set of all points within ${\displaystyle \varepsilon }$ of the set ${\displaystyle X}$ (sometimes called the ${\displaystyle \varepsilon }$-fattening of ${\displaystyle X}$ or a generalized ball of radius ${\displaystyle \varepsilon }$ around ${\displaystyle X}$).

Equivalently,

${\displaystyle d_{H}(X,Y)=\sup _{w\in M}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|=\sup _{w\in X\cup Y}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|,}$[1]

that is, ${\displaystyle d_{\mathrm {H} }(X,Y)=\sup _{w\in M}|d(w,X)-d(w,Y)|}$, where ${\displaystyle d(w,X)}$ is the distance from the point ${\displaystyle w}$ to the set ${\displaystyle X}$.

### Remark

It is not true for arbitrary subsets ${\displaystyle X,Y\subset M}$ that ${\displaystyle d_{\mathrm {H} }(X,Y)=\varepsilon }$ implies

${\displaystyle X\subseteq Y_{\varepsilon }\ {\mbox{and}}\ Y\subseteq X_{\varepsilon }.}$

For instance, consider the metric space of the real numbers ${\displaystyle \mathbb {R} }$ with the usual metric ${\displaystyle d}$ induced by the absolute value,

${\displaystyle d(x,y):=|y-x|,\quad x,y\in \mathbb {R} .}$

Take

${\displaystyle X:=(0,1]\quad {\mbox{and}}\quad Y:=[-1,0).}$

Then ${\displaystyle d_{\mathrm {H} }(X,Y)=1\ }$. However ${\displaystyle X\nsubseteq Y_{1}}$ because ${\displaystyle Y_{1}=[-2,1)\ }$, but ${\displaystyle 1\in X}$.

But it is true that ${\displaystyle X\subseteq {\overline {Y_{\varepsilon }}}}$ and ${\displaystyle Y\subseteq {\overline {X_{\varepsilon }}}}$ ; in particular it is true if ${\displaystyle X,Y}$ are closed.

## Properties

• In general, ${\displaystyle d_{\mathrm {H} }(X,Y)}$ may be infinite. If both X and Y are bounded, then ${\displaystyle d_{\mathrm {H} }(X,Y)}$ is guaranteed to be finite.
• ${\displaystyle d_{\mathrm {H} }(X,Y)=0}$ if and only if X and Y have the same closure.
• For every point x of M and any non-empty sets Y, Z of M: d(x,Y) d(x,Z) + dH(Y,Z), where d(x,Y) is the distance between the point x and the closest point in the set Y.
• |diameter(Y)-diameter(X)| dH(X,Y).[4]
• If the intersection X ? Y has a non-empty interior, then there exists a constant r > 0, such that every set X? whose Hausdorff distance from X is less than r also intersects Y.[5]
• On the set of all subsets of M, dH yields an extended pseudometric.
• On the set F(M) of all non-empty compact subsets of M, dH is a metric.
• If M is complete, then so is F(M).[6]
• If M is compact, then so is F(M).
• The topology of F(M) depends only on the topology of M, not on the metric d.

## Motivation

The definition of the Hausdorff distance can be derived by a series of natural extensions of the distance function ${\displaystyle d(x,y)}$ in the underlying metric space M, as follows:[7]

• Define a distance function between any point x of M and any non-empty set Y of M by:
${\displaystyle d(x,Y)=\inf\{d(x,y)\mid y\in Y\}.\ }$
For example, d(1, {3,6}) = 2 and d(7, {3,6}) = 1.
• Define a distance function between any two non-empty sets X and Y of M by:
${\displaystyle d(X,Y)=\sup\{d(x,Y)\mid x\in X\}.\ }$
For example, ${\textstyle d(\{1,7\},\{3,6\})=\sup\{d(1,\{3,6\}),d(7,\{3,6\})\}=\sup\{d(1,3),d(7,6)\}=2.}$
• If X and Y are compact then d(X,Y) will be finite; d(X,X)=0; and d inherits the triangle inequality property from the distance function in M. As it stands, d(X,Y) is not a metric because d(X,Y) is not always symmetric, and does not imply that (It does imply that ${\displaystyle X\subseteq Y}$). For example, , but . However, we can create a metric by defining the Hausdorff distance to be:
${\displaystyle d_{\mathrm {H} }(X,Y)=\max\{d(X,Y),d(Y,X)\}\,.}$

## Applications

In computer vision, the Hausdorff distance can be used to find a given template in an arbitrary target image. The template and image are often pre-processed via an edge detector giving a binary image. Next, each 1 (activated) point in the binary image of the template is treated as a point in a set, the "shape" of the template. Similarly, an area of the binary target image is treated as a set of points. The algorithm then tries to minimize the Hausdorff distance between the template and some area of the target image. The area in the target image with the minimal Hausdorff distance to the template, can be considered the best candidate for locating the template in the target.[8] In computer graphics the Hausdorff distance is used to measure the difference between two different representations of the same 3D object[9] particularly when generating level of detail for efficient display of complex 3D models.

## Related concepts

A measure for the dissimilarity of two shapes is given by Hausdorff distance up to isometry, denoted DH. Namely, let X and Y be two compact figures in a metric space M (usually a Euclidean space); then DH(X,Y) is the infimum of dH(I(X),Y) along all isometries I of the metric space M to itself. This distance measures how far the shapes X and Y are from being isometric.

The Gromov-Hausdorff convergence is a related idea: we measure the distance of two metric spaces M and N by taking the infimum of ${\displaystyle d_{\mathrm {H} }(I(M),J(N))}$ along all isometric embeddings ${\displaystyle I\colon M\to L}$ and ${\displaystyle J\colon N\to L}$ into some common metric space L.

## References

1. ^ a b Rockafellar, R. Tyrrell; Wets, Roger J-B (2005). Variational Analysis. Springer-Verlag. p. 117. ISBN 3-540-62772-3.
2. ^ Bîrsan, Temistocle; Tiba, Dan (2006), "One hundred years since the introduction of the set distance by Dimitrie Pompeiu", in Ceragioli, Francesca; Dontchev, Asen; Futura, Hitoshi; Marti, Kurt; Pandolfi, Luciano (eds.), System Modeling and Optimization, 199, Boston: Kluwer Academic Publishers, pp. 35-39, doi:10.1007/0-387-33006-2_4, ISBN 978-0-387-32774-7, MR 2249320
3. ^ Munkres, James (1999). Topology (2nd ed.). Prentice Hall. pp. 280-281. ISBN 0-13-181629-2.
4. ^ Diameter and Hausdorff Distance, Math.SE
5. ^ Hausdorff Distance and Intersection, Math.SE
6. ^ Henrikson, Jeff (1999). "Completeness and total boundedness of the Hausdorff metric" (PDF). MIT Undergraduate Journal of Mathematics: 69-80. Archived from the original (PDF) on June 23, 2002.
7. ^ Barnsley, Michael (1993). Fractals Everywhere. Morgan Kaufmann. pp. Ch. II.6. ISBN 0-12-079069-6.
8. ^ Hausdorff-Based Matching
9. ^ Cignoni, P.; Rocchini, C.; Scopigno, R. (1998). "Metro: Measuring Error on Simplified Surfaces". Computer Graphics Forum. 17 (2): 167-174. CiteSeerX 10.1.1.95.9740. doi:10.1111/1467-8659.00236.