A constant-factor approximation of the Gromov-Hausdorff distance in the plane (opens in new tab)

We give the first polynomial-time constant-factor approximation of the Gromov--Hausdorff distance $d_{GH}$ between finite point sets in the Euclidean plane; in fixed Euclidean dimension such an approximation was previously known only on the line (Majhi, Vitter, and Wenk, 2024). Its engine is the bijective (bottleneck) Gromov--Hausdorff distance $d_{GH}^{bij}$: for two equal-size sets the least additive distortion $\max_{i,j}|d_X(i,j) - d_Y(\sigm...