A constant-factor approximation of the Gromov-Hausdorff distance in the plane
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). Global alignment cannot succeed: the classical dimension drop defeats alignment by isometries, a multiplicity gap defeats alignment by bijections, and a reflection barrier defeats sorting under any single global reflection pattern. The algorithm is therefore local. Guessing the images of one diameter pair pins every point's longitudinal coordinate to within O(d_GH). Heights are read in windows whose height spread is at most a fixed multiple of their length, where a chain argument makes every compatible match local in the plane. One reflection sign per window is then chosen by 2-SAT; at the right frame and guess, any solution yields a correspondence of distortion O(d_GH). For the bijective relative of d_GH, half the least additive distortion over bijections, the same scheme reduces the planar problem to a matching question that we leave open.
Related
- Pointed Gromov-Hausdorff Distance between lp-Wedge Sums and Isometric Embeddings of l∞
- Gromov--Hausdorff Distance Between Euclidean Unit Balls
- Modifications of the Continuous Gromov--Hausdorff Distance
- Gromov-Hausdorff Convergence of Constant Scalar Curvature Kähler Metrics near the Canonical Class
- Gromov-Hausdorff distance and stability of dynamical systems
BibTeX
@misc{majhi2026constantfactor,
title = {{A constant-factor approximation of the Gromov-Hausdorff distance in the plane}},
author = {Sushovan Majhi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.17051},
eprint = {2606.17051},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.17051},
}
RIS
TY - UNPB
TI - A constant-factor approximation of the Gromov-Hausdorff distance in the plane
AU - Sushovan Majhi
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2606.17051
UR - https://arxiv.org/abs/2606.17051
AB - 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). Global alignment cannot succeed: the classical dimension drop defeats alignment by isometries, a multiplicity gap defeats alignment by bijections, and a reflection barrier defeats sorting under any single global reflection pattern. The algorithm is therefore local. Guessing the images of one diameter pair pins every point's longitudinal coordinate to within O(d_GH). Heights are read in windows whose height spread is at most a fixed multiple of their length, where a chain argument makes every compatible match local in the plane. One reflection sign per window is then chosen by 2-SAT; at the right frame and guess, any solution yields a correspondence of distortion O(d_GH). For the bijective relative of d_GH, half the least additive distortion over bijections, the same scheme reduces the planar problem to a matching question that we leave open.
ER -