Hausdorff distance

For nonempty bounded subsets of a metric space,This is a metric on the nonempty closed bounded subsets. Without closedness it is only a pseudometric: a set and its closure have distance zero.

For any nonempty complete metric space $X$, the family of its nonempty closed bounded subsets is a complete metric space under the Hausdorff distance. Boundedness of the entire ambient space is unnecessary in this general form.

For a Cauchy sequence $(F_n)$ of these sets, define $A_n=\overline{{\bigcup }_{m\ge n}{F}_m}$ and ${\delta }_n={\sup }_{p,q\ge n}{d}_H(F_p,F_q)$. A Cauchy sequence in any metric space is bounded, so its tail sets are contained in a common finite-radius neighbourhood of one bounded $F_N$; hence every $A_n$ is bounded. The distance to a set is one-Lipschitz, so estimates pass to the closure, giving $d_H(F_n,A_n)\le {\delta }_n$ and $d_H(A_n,A_m)\le {\delta }_n$ for $m\ge n$. Choose $n_j$ with ${\delta }_{n_j}\le 2^{-j}$. The Summably nested Hausdorff intersection theorem gives $A_{n_j}\to G\ne \varnothing$. The triangle inequality now gives $F_n\to G$, proving completeness.

Let $X$ be a complete metric space and let $F_n$ be nonempty closed bounded subsets with $F_{n+1}\subseteq F_n$ and Hausdorff distance $d_H(F_n,F_{n+1})\le a_n$, where $a_n\ge 0$ and ${\sum }_n{a}_n<\infty$. Then $G={\bigcap }_n{F}_n$ is nonempty and closed, and $d_H(F_n,G)\le {\sum }_{k=n}^{\infty }{a}_k\to 0$.

To prove this, start with any $x_n\in F_n$ and choose $x_{k+1}\in F_{k+1}$ with $d(x_k,x_{k+1})<a_k+\eta 2^{n-k-1}$. The triangle inequality makes the resulting sequence a Cauchy sequence. Its limit exists by completeness and belongs to every $F_j$ by nesting and closedness. Its distance from the starting point is at most ${\sum }_{k=n}^{\infty }{a}_k+\eta$. Let $\eta \downarrow 0$ and take the supremum over starting points. The reverse directed distance is zero since $G\subseteq F_n$. Unlike the usual shrinking-diameter form of Cantor's intersection theorem, the sets need not have diameters tending to zero.

The map $x\mapsto \{x\}$ is an isometry into the hyperspace of nonempty closed bounded subsets. Its image is closed because a Hausdorff limit of singletons has diameter zero and is therefore a singleton.

If the Hausdorff hyperspace is complete, its closed subspace of singletons is complete. Since that subspace is isometric to the original metric space, the original space is complete as well.

For compact metric spaces $X$ and $Y$, the Gromov-Hausdorff distance iswhere the infimum runs over all metric spaces $Z$ and all isometric embeddings $\phi :X\to Z$ and $\psi :Y\to Z$. It measures how closely the two spaces can be placed inside one ambient metric space.

The Gromov-Hausdorff topology on isometry classes of compact metric spaces is the topology induced by the Gromov-Hausdorff distance.

A real tree is a metric space $(T,d)$ in which every pair $a,b\in T$ is joined by a unique arc and that arc is isometric to the real interval $[0,d(a,b)]$. Equivalently, it is a geodesic metric space with no nontrivial simple loops.

The multiplicity of $a$ in a real tree $T$ is the number of connected components of $T\setminus \{a\}$. A point of multiplicity one is a leaf, one of multiplicity two lies in the interior of an unbranched arc, and one of multiplicity at least three is a branch point.

Let $g:[0,1]\to {\mathbb{R}}_{+}$ be continuous with $g(0)=g(1)=0$, and setThe function $d_g$ is a pseudometric. Its metric quotientis the real tree encoded by $g$.

Every compact real tree is isometric to a real tree encoded by an excursion. One construction takes finite subtrees spanning successively finer finite nets, performs depth-first contour traversals of those subtrees, and chooses compatible time parameterizations. The contour functions have a uniformly convergent subsequence, and continuity of excursion coding in the Gromov-Hausdorff distance identifies the limiting coded tree with the original tree.