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). 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.17051
curl -X POST /api/v1/records/arxiv/2606.17051/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.17051/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'