Hausdorff distance

From Wikipedia, the free encyclopedia

The Hausdorff distance, or Hausdorff metric, measures how far two compact non-empty subsets of a metric space are from each other. It is named after Felix Hausdorff.

[edit] Definitions

Let X and Y be two compact subsets of a metric space M. The Hausdorff distance d_H(X,Y) is the minimal number r such that the closed r-neighborhood of X contains Y and the closed r-neighborhood of Y contains X. In other words, if d(x, y) denotes the distance in M, then

$d_{\mathrm H}(X,Y) = \max\{\,\sup_{x \in X} \inf_{y \in Y} d(x,y),\, \sup_{y \in Y} \inf_{x \in X} d(x,y)\,\}\mbox{.} \!$

This distance function turns the set of all non-empty compact subsets of M into a metric space, say F(M). The topology of F(M) depends only on the topology of M. If M is compact, then so is F(M).

Hausdorff distance can be defined in essentially the same way for non-empty closed and bounded subsets of M, but taking an infimum over r instead of a minimum. (In a general metric space, closed and bounded subsets are more general than compact subsets. For instance in the space of continuous real-valued functions on [0,1] metrized with the sup-norm, the closed unit ball is closed and bounded but not compact.) If we allow closed unbounded subsets then the distance may take infinite values. When working with non-compact subsets, the topology of F(M) depends on the metric on M and not only on its topology. The Hausdorff distance between general subsets can be defined as the Hausdorff distance between their closures. It gives a pre-metric (or pseudometric) on the set of all subsets of M (the Hausdorff distance between any two sets with the same closure is zero).

In Euclidean geometry, one often uses an analog, Hausdorff distance up to isometry. Namely, let X and Y be two compact figures in a Euclidean space; then D_H(X,Y) is the minimum of d_H(I(X),Y) along all isometries I of Euclidean space. This distance measures how far X and Y are from being isometric.