A constant-factor approximation of the Gromov-Hausdorff distance in the plane
2026-06-15 • Computational Geometry
Computational GeometryData Structures and Algorithms
AI summaryⓘ
The authors present the first algorithm that can quickly find a close approximation of the Gromov–Hausdorff distance between two sets of points in the plane, something only known for points on a line before. Their method focuses on approximating the bijective version of this distance, which measures how much a perfect matching between points distorts distances. They solve a previously open problem by distinguishing between 'fat' sets (handled by a rigid motion) and nearly straight sets (handled by clustering and reflections). Their analysis also shows why each part of their approach is necessary through matching lower bounds.
Gromov–Hausdorff distanceEuclidean planePolynomial-time approximationBijective Gromov–Hausdorff distanceAdditive distortionRigid motionCluster dendrogramCorrespondencesApproximation algorithmsMetric geometry
Authors
Sushovan Majhi
Abstract
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(σi, σj)|$ of a bijection $σ$ equals $2\,d_{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.