论文标题
lipschitz（非）gromov-hausdorff距离，包括在超级空间上
Lipschitz (non-)equivalence of the Gromov--Hausdorff distances, including on ultrametric spaces
论文作者
论文摘要
Gromov-Hausdorff距离测量紧凑型公制空间之间的形状差异。即使将距离近似于任何实际因素也会提出NP障碍问题，但事实证明，它的放松对几何数据分析（包括点云，歧管和图形）的问题很有用。我们研究了修改的gromov--hausdorff距离，这是保留其许多理论特性的标准距离的松弛，其中包括它们在丰富的公制空间家族中的拓扑等效性。我们表明，这两个距离在任何统一尺寸的度量空间家庭上都是lipschitz等效的，但是等效性通常不能保持，即使距离仅限于超规模空间。我们还证明，当将标准和修改的gromov-hausdorff距离相等或彼此之间的距离相等，或者在2倍以内，这将放松与离散几何形状中的一些众所周知的问题联系在一起。
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.
