Approximating Gromov-Hausdorff Distance in Euclidean Space

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