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 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

For each pair of non-empty subsets

represents the supremum operator,

quantifies the distance from a point

or a generalized ball of radius

) := inf { ε ≥ 0 ∣

is the smallest distance from the point

It is not true for arbitrary subsets

implies For instance, consider the metric space of the real numbers

induced by the absolute value, Take Then

The definition of the Hausdorff distance can be derived by a series of natural extensions of the distance function

in the underlying metric space M, as follows:[7] 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.

In computer graphics the Hausdorff distance is used to measure the difference between two different representations of the same 3D object[8] particularly when generating level of detail for efficient display of complex 3D models.

is the land-surface of Earth, then by finding the point Nemo, we see

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) among 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: measuring the distance of two metric spaces M and N by taking the infimum of

into some common metric space L.