Hausdorff Distance

In mathematics, the Hausdorff distance, or Hausdorff metric, also called Pompeiu–Hausdorff distance, 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 someone can be forced to travel by an adversary who chooses a point in one of the two sets, from where they 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.

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 ,1\to \R^3.

Definition

Let $(M,d)$ be a metric space. For each pair of non-empty subsets $X \subset M$ and $Y \subset M$, the Hausdorff distance between $X$ and $Y$ is defined as

$d_(X,Y) := \max\left\,$

where $\operatorname$ represents the supremum operator, $\operatorname$ the infimum operator, and where $d(a, B) := \inf_ d(a,b)$ quantifies the distance from a point $a \in X$ to the subset $B\subseteq X$.

An equivalent definition is as follows. For each set $X \subset M,$ let
$X_\varepsilon := \bigcup_ \,$
which is the set of all points within $\varepsilon$ of the set $X$ (sometimes called the $\varepsilon$-fattening of $X$ or a generalized ball of radius $\varepsilon$ around $X$).
Then, the Hausdorff distance between $X$ and $Y$ is defined as
$d_H(X,Y) := \inf\.$

Equivalently,
$\begin d_H(X, Y) &= \sup_ \left, \inf_ d(w,x) - \inf_ d(w,y)\ \\ &= \sup_ \left, \inf_ d(w,x) - \inf_ d(w,y)\ \\ &= \sup_ , d(w, X) - d(w, Y), , \end$
where $d(w, X) := \inf_ d(w,x)$ is the smallest distance from the point $w$ to the set $X$.

Remark

It is not true for arbitrary subsets $X, Y \subset M$ that $d_(X,Y) = \varepsilon$ implies
:$X\subseteq Y_\varepsilon \ \mbox \ Y\subseteq X_\varepsilon.$

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

:$d(x,y) := , y - x, , \quad x,y \in \R.$

Take

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

Then $d_(X,Y) = 1\$. However $X \nsubseteq Y_1$ because $Y_1 = [-2,1)\$, but $1 \in X$.

But it is true that $X\subseteq \overline$ and $Y\subseteq \overline$ ; in particular it is true if $X, Y$ are closed.

Properties

* In general, $d_\text(X, Y)$ may be infinite. If both ''X'' and ''Y'' are bounded set, bounded, then $d_\text(X, Y)$ is guaranteed to be finite.
* $d_\text(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'') + ''d''_H(''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''), ≤ 2''d''_H(''X'', ''Y'').
* 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''.
* On the set of all subsets of ''M'', ''d''_H yields an extended pseudometric.
* On the set ''F''(''M'') of all non-empty compact subsets of ''M'', ''d''_H is a metric.
** If ''M'' is complete, then so is ''F''(''M'').
** 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 $d(x,y)$ in the underlying metric space ''M'', as follows:
* Define a distance function between any point ''x'' of ''M'' and any non-empty set ''Y'' of ''M'' by triangle inequality