Hausdorff distance
The Hausdorff distance is a measure of the separation between two nonempty subsets of a metric space. Rather than comparing selected points or designated centers, it measures the largest distance that a point of either set must travel to approach the other set. On suitable families of closed subsets, this construction defines a metric and thereby supplies a topology for the study of set-valued convergence.
The distance is named after Felix Hausdorff, who incorporated it into the systematic development of metric and topological set theory in his 1914 work Grundzüge der Mengenlehre. Closely related constructions had appeared in the earlier work of Dimitrie Pompeiu, and the resulting metric is consequently also called the Pompeiu–Hausdorff distance.
Definition
Let ((X,d)) be a metric space, and let (A) and (B) be nonempty subsets of (X). The distance from a point (x\in X) to a subset (B) is
[ d(x,B)=\inf_{b\in B} d(x,b). ]
The directed excess of (A) over (B) is defined by
[ e(A,B)=\sup_{a\in A} d(a,B) =\sup_{a\in A}\inf_{b\in B}d(a,b). ]
This quantity is generally asymmetric because points of (A) may all lie near (B) even when some points of (B) lie far from (A). The Hausdorff distance removes this asymmetry by taking the larger of the two directed excesses:
[ d_{\mathrm H}(A,B)
\max{e(A,B),e(B,A)}. ]
Equivalently,
[ d_{\mathrm H}(A,B)
\max \left{ \sup_{a\in A}\inf_{b\in B}d(a,b), \sup_{b\in B}\inf_{a\in A}d(a,b) \right}. ]
The value may be infinite when unbounded subsets are considered in an unbounded metric space. It is finite for every pair of nonempty bounded subsets.
For (r\geq 0), let
[ B_r={x\in X:d(x,B)\leq r} ]
denote the closed (r)-neighborhood of (B). The Hausdorff distance also has the neighborhood characterization
[ d_{\mathrm H}(A,B)
\inf{r\geq 0:A\subseteq B_r\text{ and }B\subseteq A_r}. ]
Thus, (d_{\mathrm H}(A,B)\leq r) precisely when each set is contained in the closed (r)-neighborhood of the other.
Metric properties
Symmetry follows directly from the definition:
[ d_{\mathrm H}(A,B)=d_{\mathrm H}(B,A). ]
The triangle inequality is inherited from the ambient metric. For nonempty subsets (A,B,C\subseteq X),
[ e(A,C)\leq e(A,B)+e(B,C), ]
and the corresponding inequality with the directions reversed yields
[ d_{\mathrm H}(A,C) \leq d_{\mathrm H}(A,B)+d_{\mathrm H}(B,C). ]
If arbitrary subsets are admitted, zero Hausdorff distance does not necessarily imply literal equality. Instead,
[ d_{\mathrm H}(A,B)=0 \quad\Longleftrightarrow\quad \overline{A}=\overline{B}, ]
where the bars denote topological closure. The Hausdorff distance is therefore a pseudometric on bounded nonempty subsets and becomes a genuine metric when restricted to bounded nonempty closed subsets.
For singleton sets, the construction reproduces the original metric:
[ d_{\mathrm H}({x},{y})=d(x,y). ]
Consequently, the map (x\mapsto{x}) embeds (X) isometrically into the corresponding space of closed subsets.
The distance is unchanged after closure:
[ d_{\mathrm H}(A,B)
d_{\mathrm H}(\overline A,\overline B). ]
This identity accounts for the natural restriction to closed sets and explains why nonclosed sets with the same closure cannot be distinguished by the metric.
Distance-function representation
Each nonempty subset (A\subseteq X) determines a real-valued distance function
[ \delta_A(x)=d(x,A). ]
Every such function is Lipschitz continuous with Lipschitz constant (1). When the Hausdorff distance is finite, it satisfies
[ d_{\mathrm H}(A,B)
\sup_{x\in X} \left| \delta_A(x)-\delta_B(x) \right|. ]
The Hausdorff distance can therefore be interpreted as the uniform distance between the distance functions generated by the two sets. This representation connects convergence of sets with uniform convergence of functions and makes the triangle inequality an immediate consequence of the corresponding inequality for the supremum norm.
In a 1921 treatment of compact-set convergence, You Watanabe formulated mutual neighborhood containment in terms of these distance functions and established its equivalence to uniform convergence of (\delta_A) on compact ambient spaces. This formulation became part of the early hyperspace interpretation of Hausdorff convergence.
Hausdorff convergence
A sequence of nonempty closed bounded subsets ((A_n)) converges to (A) in Hausdorff distance when
[ d_{\mathrm H}(A_n,A)\longrightarrow 0. ]
This condition means that every point of (A_n) eventually lies uniformly close to (A), while every point of (A) simultaneously lies uniformly close to (A_n). Neither directed condition alone is sufficient because one-sided convergence permits portions of one set to remain unmatched.
In terms of distance functions, Hausdorff convergence is expressed by
[ \sup_{x\in X} \left| d(x,A_n)-d(x,A) \right| \longrightarrow 0. ]
When (X) is compact, the space (\mathcal K(X)) of nonempty compact subsets of (X), equipped with (d_{\mathrm H}), is itself compact. If (X) is complete, then (\mathcal K(X)) is complete under the Hausdorff metric. These properties place compact subsets within the framework of hyperspaces, whose points are themselves subsets of another topological space.
For compact convex subsets of Euclidean space, Hausdorff convergence is closely associated with the Blaschke selection theorem. Wilhelm Blaschke developed this compactness principle in the study of convex bodies, where a uniformly bounded sequence admits a Hausdorff-convergent subsequence under the theorem’s standard hypotheses.
Behavior in Euclidean space
For nonempty compact subsets of (\mathbb R^n), the Euclidean metric makes every directed excess finite and ensures that the infima and suprema in the definition are attained. The Hausdorff distance then equals the greatest among the nearest-set distances realized by points of the two sets.
For closed intervals (A=[a,b]) and (B=[c,d]) in (\mathbb R),
[ d_{\mathrm H}(A,B)
\max{|a-c|,\lvert b-d\rvert}. ]
The formula shows that Hausdorff convergence of closed intervals is equivalent to convergence of both endpoints.
A translation by a vector (v\in\mathbb R^n) preserves the distance between corresponding translated sets:
[ d_{\mathrm H}(A+v,B+v)=d_{\mathrm H}(A,B). ]
More generally, every isometry (f:X\to X) satisfies
[ d_{\mathrm H}(f(A),f(B))=d_{\mathrm H}(A,B). ]
Scaling in a normed vector space changes the distance by the absolute value of the scale factor:
[ d_{\mathrm H}(\lambda A,\lambda B)
|\lambda|,d_{\mathrm H}(A,B). ]
Sensitivity to remote points
The Hausdorff distance depends on the largest nearest-set discrepancy. A single isolated point located far from the remainder of a set can therefore determine the entire distance, even when the remaining portions of the compared sets coincide.
For example, let (A=[0,1]) and (B=[0,1]\cup{R}) in (\mathbb R), where (R>1). Every point of (A) belongs to (B), so (e(A,B)=0). The isolated point (R) lies at distance (R-1) from (A), giving
[ d_{\mathrm H}(A,B)=R-1. ]
This behavior reflects the uniform character of Hausdorff convergence. It distinguishes the Hausdorff metric from comparison methods based on averages, probability measures, or partial correspondences.
Relation to other distances
The Gromov–Hausdorff distance compares compact metric spaces without requiring them to be subsets of a common ambient space. It does so by considering isometric embeddings into shared metric spaces and then taking an infimum of the resulting Hausdorff distances.
For finite point sets, the Hausdorff distance differs from matching-based constructions because it does not require a bijection between points. Several points of one set may have the same nearest point in the other set. The metric consequently records mutual geometric coverage rather than a prescribed point-to-point correspondence.
In mathematical morphology, closed neighborhoods underlying the Hausdorff definition are expressed through Minkowski addition. In Euclidean space, the condition (A\subseteq B_r) can be written as
[ A\subseteq B+r\overline{\mathbb B}, ]
where (\overline{\mathbb B}) is the closed unit ball. This representation links Hausdorff distance with dilation operations and the geometry of parallel bodies.