# Computing the Gromov-Hausdorff Distance for Metric Trees

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2015.

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

- [Rapid and Precise Topological Comparison with Merge Tree Neural Networks](https://mlsanity.com/paper/2404.05879/) (2024)
- [The Universal ℓp-Metric on Merge Trees](https://mlsanity.com/paper/2112.12165/) (2021)
- [Fitting trees to ℓ1-hyperbolic distances](https://mlsanity.com/paper/2409.01010/) (2024)
- [Quotient Geometry and Persistence-Stable Metrics for Swarm Configurations](https://mlsanity.com/paper/2603.18041/) (2026)

## Abstract (arXiv)

The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the Gromov-Hausdorff distance better than a factor of 3 for geodesic metrics on a pair of trees. We complement this result by providing a polynomial time O(minn, √rn)-approximation algorithm for computing the GH distance between a pair of metric trees, where r is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an O(√n)-approximation algorithm.