# The Gromov-Hausdorff distance between ultrametric spaces: its structure and computation

arXiv: https://arxiv.org/abs/2110.03136 · HTML: https://mlsanity.com/paper/2110.03136/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2021.

## Built on by (most cited first, 5 of 5)

- [Recognizing Rigid Patterns of Unlabeled Point Clouds by Complete and Continuous Isometry Invariants with no False Negatives and no False Positives](https://mlsanity.com/paper/2303.15385/) (2023)
- [MCbiF: Measuring Topological Autocorrelation in Multiscale Clusterings via 2-Parameter Persistent Homology](https://mlsanity.com/paper/2510.14710/) (2025)
- [A cohomology-based Gromov-Hausdorff metric approach for quantifying molecular similarity](https://mlsanity.com/paper/2411.13887/) (2024)
- [Quotient Geometry and Persistence-Stable Metrics for Swarm Configurations](https://mlsanity.com/paper/2603.18041/) (2026)
- [Classification Fields: Arbitrarily Fine Recursive Hierarchical Clustering From Few Examples](https://mlsanity.com/paper/2605.07119/) (2026)

## Abstract (arXiv)

The Gromov-Hausdorff distance (dGH) provides a natural way of quantifying the dissimilarity between two given metric spaces. It is known that computing dGH between two finite metric spaces is NP-hard, even in the case of finite ultrametric spaces which are highly structured metric spaces in the sense that they satisfy the so-called strong triangle inequality. Ultrametric spaces naturally arise in many applications such as hierarchical clustering, phylogenetics, genomics, and even linguistics. By exploiting the special structures of ultrametric spaces, (1) we identify a one parameter family dGH(p)p∈[1,∞] of distances defined in a flavor similar to the Gromov-Hausdorff distance on the collection of finite ultrametric spaces, and in particular dGH(1) =dGH. The extreme case when p=∞, which we also denote by uGH, turns out to be an ultrametric on the collection of ultrametric spaces. Whereas for all p∈[1,∞), dGH(p) yields NP-hard problems, we prove that surprisingly uGH can be computed in polynomial time. The proof is based on a structural theorem for uGH established in this paper; (2) inspired by the structural theorem for uGH, and by carefully leveraging properties of ultrametric spaces, we also establish a structural theorem for dGH when restricted to ultrametric spaces. This structural theorem allows us to identify special families of ultrametric spaces on which dGH is computationally tractable. These families are determined by properties related to the doubling constant of metric space. Based on these families, we devise a fixed-parameter tractable (FPT) algorithm for computing the exact value of dGH between ultrametric spaces. We believe ours is the first such algorithm to be identified.