The Gromov--Hausdorff distance measures the difference in shape between compact metric spaces. While even approximating the distance up to any practical factor poses an NP-hard problem, its relaxations have proven useful for the problems in geometric data analysis, including on point clouds, manifolds, and graphs. We investigate the modified Gromov--Hausdorff distance, a relaxation of the standard distance that retains many of its theoretical properties, which includes their topological equivalence on a rich set of families of metric spaces. We show that the two distances are Lipschitz-equivalent on any family of metric spaces of uniformly bounded size, but that the equivalence does not hold in general, not even when the distances are restricted to ultrametric spaces. We additionally prove that the standard and the modified Gromov--Hausdorff distances are either equal or within a factor of 2 from each other when taken to a regular simplex, which connects the relaxation to some well-known problems in discrete geometry.
翻译:Gromov-Hausdorf 距离测量了紧凑度量空间之间的形状差异。 即使距离接近于任何实际因素, 也带来了NP- 硬问题, 但它的放松对于几何数据分析问题, 包括点云、 方块和图形等方面的问题, 证明是有用的。 我们调查了经修改的Gromov-Hausdorf 距离, 保持了它许多理论特性的标准距离, 包括它们对于一组丰富度量空间的大家庭的等同性。 我们显示, 这两条距离对于一个统一度量空间的大家庭来说, Lipschitz 都相当于 Lipschitz, 但这种等同并不普遍, 即使在距离限制在超度空间时也是如此。 我们还进一步证明, 标准以及经修改的Gromov-Hausdorf 距离, 当被带入一个普通的简单点时, 或者在2个系数之内,, 也就是将放松与一些已知的离地测量问题联系起来。