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.

v2: New proof (frames, windows and 2-SAT) replacing the dendrogram argument of v1, which had gaps. The main theorem for d_GH is unchanged in statement and now has an explicit constant. The constant-factor approximation of the bijective distance claimed in v1 is withdrawn and left open. Attribution of the dimension-drop example corrected. 17 pages, 3 figures