{"id":"arxiv/2606.17051","url":"https://arxiv.org/abs/2606.17051","tags":["cs.CG","cs.DS","math.MG"],"score":0,"title":"A constant-factor approximation of the Gromov-Hausdorff distance in the plane","domain":"cs.CG","source":"arxiv","authors":["Sushovan Majhi"],"reviews":0,"subject":"cs.CG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-15","reactions":{}}