The Hausdorff distance $d_H(A, B)$ between two subsets of a metric space is intuitive: it is the smallest ε such that every point of A is within ε of some point of B, and vice versa. Think of it as "how far apart are these two clouds of points in the same room."

The Gromov–Hausdorff distance $d_{\mathrm{GH}}(X, Y)$ asks something harder: given two metric spaces that may have no natural common embedding, how similar are they intrinsically? We want to compare the shapes of a circle and a square without embedding either into ℝ² first. $d_{\mathrm{GH}}$ is defined as the infimum of $d_H(f(X), g(Y))$ over all isometric embeddings f, g into any common space Z.

Given isometric embeddings f: X → Z and g: Y → Z, the Hausdorff distance $d_H(f(X), g(Y))$ is computed in the ambient space $Z$. By definition of $d_{\mathrm{GH}}$ as an infimum over all such embeddings:

This gives the upper bound for any particular embedding. The content of the theorem is identifying when the infimum is achieved — when the specific Hausdorff distance of a given embedding equals $d_{\mathrm{GH}}$.

The lower bound uses the correspondence formulation. A correspondence R ⊆ X × Y is a relation that "covers" both spaces: every x ∈ X appears in some pair (x, y) ∈ R and every y ∈ Y appears in some (x, y) ∈ R. The distortion of R is:

McBride, Majhi, Adams, and Frick show that for compact spaces there always exists a correspondence whose distortion is bounded below by the Hausdorff distance of the spaces viewed as subsets of their own disjoint union. Combined with $d_{\mathrm{GH}} = \tfrac{1}{2}\inf_R\,\mathrm{dis}(R)$, this gives the lower bound. The factor $\tfrac{1}{2}$ is shown to be tight by an explicit construction: two spaces (e.g., a segment and a point) where the GH distance is exactly half the Hausdorff distance.

The main technical contribution is characterizing when $d_{\mathrm{GH}}(X, Y) = d_H(f(X), g(Y))$ for the "natural" embedding. The paper proves that equality holds whenever the spaces satisfy an intrinsic flatness condition: informally, the metric geometry of X and Y is locally Euclidean in a quantified sense near the "closest pair" of points.

More precisely, the condition involves comparing the spread of each space — a measure of how much the pairwise distances vary — to the Hausdorff distance. When the spread is small relative to $d_H$, the bound is tight. This gives a practical criterion: if you compute d_H in some embedding and the spaces are "nearly flat," you can trust that $d_H$ gives the exact $d_{\mathrm{GH}}$.

The GH distance is the natural metric for comparing persistent homology barcodes — the output of TDA pipelines. Computing $d_{\mathrm{GH}}$ exactly is NP-hard in general. This theorem gives a polynomial-time computable upper bound (via d_H in any convenient embedding) and a matching lower bound (d_H / 2).

In practice this means: given two datasets whose Vietoris-Rips complexes you want to compare, you can embed both into a common Euclidean space, compute $d_H$ (trivial), and obtain a factor-2 approximation to $d_{\mathrm{GH}}$. The sharpness result tells you exactly when this approximation is exact — which for many practically relevant datasets (e.g., point clouds sampled from flat manifolds) it is.

This connects directly to the UMAP thesis: the GH distance controls the quality of the UMAP embedding, and this paper provides the tools to certify when that embedding is near-optimal.