Computing the Gromov-Hausdorff Distance for Metric Trees

2015/09/18 by Agarwal, Pankaj K., Fox, Kyle, Nath, Abhinandan +2 · 5 citations
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1509.05751

Abstract

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(min\n, √(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.

Cited by

• Locally Correct Interleavings between Merge Trees
• Guaranteeing Hausdorff-Gromov-Hausdorff Equality for Metric Graphs
• Efficient Heuristic Algorithms for Interleaving Distance between Merge Trees
• Intrinsic Bottleneck Distance for Merge Trees
• Gromov-Hausdorff distance between chromatic metric pairs and stability of the six-pack

Related

• FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
• Gromov-Hausdorff Geometry of Metric Trees
• A polynomial-time relaxation of the Gromov-Hausdorff distance
• Computing the Gromov--Hausdorff distance using gradient methods
• Gromov--Hausdorff Distance to Simplexes