RECORD
A constant-factor approximation of the Gromov-Hausdorff distance in the plane
Computational Geometry · Submitted 15 Jun 2026
abstract compiled · 2026-09-24 · no language-model review
The authors' main claim 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).
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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). | contribution 0.96 | 0.96 | 0.92 | asserted 1.00 |
| s1 | 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. | interpretation 0.41 | 0.50 | 0.04 | asserted 1.00 |
| s2 | The algorithm is therefore local. | method 0.71 | 0.56 | 0.06 | asserted 1.00 |
| s3 | Guessing the images of one diameter pair pins every point's longitudinal coordinate to within O(d_GH). | method 0.99 | 0.86 | 0.07 | asserted 1.00 |
| s4 | 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. | method 1.00 | 0.88 | 0.06 | asserted 1.00 |
| s5 | 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). | method 0.93 | 0.91 | 0.24 | asserted 0.88 |
| s6 | 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. | limitation 0.50 | 0.73 | 0.05 | asserted 0.95 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
References
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.