Cutting a convex body into fat parts and approximating Euclidean distance by graph distances
Can one construct a graph $G$ on the set of integer points ${\mathbb Z}^2$ in the plane such that the length of the shortest path between any two vertices of $G$ differs from their Euclidean distance by at most an absolute constant? This question of Benjamini, Erd\H os, Kleiner, Kozma, Schramm, and the first-named author has been open for a long time. We give an affirmative answer to a weaker form of this question, based on the following geometric statement, which is of independent interest. There exists a constant $c>0$ such that for every $i=1,2,\ldots,$ every $ρ$-fat plane convex set $S$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.20702
curl -X POST /api/v1/records/arxiv/2609.20702/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.20702/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'