{"ID":23620895,"CreatedAt":"2026-09-18T06:47:37.825099056Z","UpdatedAt":"2026-09-18T06:47:37.825099056Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20702","arxiv_id":"2609.20702","title":"Cutting a convex body into fat parts and approximating Euclidean distance by graph distances","abstract":"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\u003e0$ such that for every $i=1,2,\\ldots,$ every $ρ$-fat plane convex set $S$ can be cut into $2^i$ convex pieces of equal area, each of which is at least $cρ$-fat. (A convex set is $ρ$-fat if the ratio of its inradius to its circumradius is at least $ρ$.) We prove that there exists an (unweighted) spanning subgraph $G$ of an enlarged copy of ${\\mathbb Z}^2$ such that, for every pair of vertices at Euclidean distance $d$, their shortest-path distance in $G$ lies between $d-O(1)$ and $d+o(d^{5/6})$. The same bound can be achieved by a planar graph with vertex set ${\\mathbb Z}^2$, in which every edge joins two vertices at Euclidean distance at most 2.","short_abstract":"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 auth...","url_abs":"https://arxiv.org/abs/2609.20702","url_pdf":"https://arxiv.org/pdf/2609.20702v1","authors":"[\"János Pach\",\"Gábor Tardos\"]","published":"2026-09-17T17:04:15Z","proceeding":"math.CO","tasks":"[\"math.CO\"]","methods":"[]","has_code":false}