# Approximating Gromov-Hausdorff Distance in Euclidean Space

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2019.

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

- [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)

## Abstract (arXiv)

The Gromov-Hausdorff distance (dGH) proves to be a useful distance measure between shapes. In order to approximate dGH for compact subsets X,Ysubsetℝd, we look into its relationship with dH,iso, the infimum Hausdorff distance under Euclidean isometries. As already known for dimension d≥ 2, the dH,iso cannot be bounded above by a constant factor times dGH. For d=1, however, we prove that dH,iso≤frac54dGH. We also show that the bound is tight. In effect, this gives rise to an O(nlogn)-time algorithm to approximate dGH with an approximation factor of left(1+frac14right).