A constant-factor approximation of the Gromov-Hausdorff distance in the plane

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}\mathrm{\mid }{d}_X(i,j)-d_Y(\sigma i,\sigma j)\mathrm{\mid }$ of a bijection $\sigma$ equals $2d_{GH}^{bij}$, which we likewise approximate within an absolute constant. Approximating additive distortion goes back to Hall and Papadimitriou (2005), who gave a $2$-approximation on the line and observed approximation within $3$ to be NP-hard in dimension three; the planar case they left open is the one we settle. A fat-or-collinear dichotomy drives both bounds: a fat set is aligned by a single rigid motion, while a near-collinear set is split into clusters matched along their dendrogram in one flat, scale-free pass, with relative orientations and per-node reflection signs – at every scale of the dendrogram – recovered by global cuts. Relaxing bijections to correspondences yields $d_{GH}$ itself, which reduces to a lone within-cluster-multiplicity kernel – the pairs an optimal correspondence collapses – that the same theory closes. Matching lower bounds – a dimension drop, a multiplicity gap, and a reflection barrier acting at every scale – show each ingredient is necessary.