Approximating Gromov-Hausdorff Distance in Euclidean Space
share
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⊂R^d, we look into its relationship with d_H,iso, the infimum Hausdorff distance under Euclidean isometries. As already known for dimension d≥ 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≤5/4d_GH. We also show that the bound is tight. In effect, this gives rise to an O(nlogn)-time algorithm to approximate d_GH with an approximation factor of (1+1/4).
READ FULL TEXT