Approximating Gromov-Hausdorff Distance in Euclidean Space

Abstract

The Gromov-Hausdorff distance $(d_{GH})$ proves to be a useful distance measure between shapes. In order to approximate $d_{GH}$ for compact subsets $X,Y\subset {\mathbb{R}}^d$, we look into its relationship with $d_{H,iso}$, the infimum Hausdorff distance under Euclidean isometries. As already known for dimension $d\ge 2$, the $d_{H,iso}$ cannot be bounded above by a constant factor times $d_{GH}$. For $d=1$, however, we prove that $d_{H,iso}\le \frac{5}{4}{d}_{GH}$. We also show that the bound is tight. In effect, this gives rise to an $O(n\log n)$-time algorithm to approximate $d_{GH}$ with an approximation factor of $\left(1+\frac{1}{4}\right)$.

Cited by in corpus (2)

• Polynomial-time algorithms for continuous metrics on atomic clouds of unordered points
• The Gromov-Hausdorff distance between ultrametric spaces: its structure and computation