Euclidean vs Graph Metric: The Fixed-Source Problem

Itai Benjamini

arxiv: 2606.13271 · v2 · pith:OB335KHEnew · submitted 2026-06-11 · 🧮 math.MG

Euclidean vs Graph Metric: The Fixed-Source Problem

Itai Benjamini This is my paper

Pith reviewed 2026-06-27 05:06 UTC · model grok-4.3

classification 🧮 math.MG

keywords Euclidean metricgraph metricplanar graphs10-netdistance approximationbounded degree

0 comments

The pith

Two fixed sources in the Euclidean plane can be realized by a bounded-degree planar unit-edge graph on a 10-net, with graph distance from each source agreeing with Euclidean distance up to a universal additive constant.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for any two fixed points chosen in advance, there exists a planar graph of bounded degree whose vertices lie on a 10-net and whose edges all have length one, such that the shortest-path distance in the graph from every vertex to each of the two chosen points differs from the Euclidean distance by at most a fixed additive constant independent of the points. The graph is permitted to depend on the locations of the two sources. The same statement is left open for three non-collinear sources, while a logarithmic lower bound is shown for the number of sources that can be handled simultaneously when the graph is required to be coordinate-planar.

Core claim

Two fixed sources in the Euclidean plane can be realized by a bounded-degree planar unit-edge graph on a 10-net, with graph distance from each source agreeing with Euclidean distance up to a universal additive constant.

What carries the argument

A bounded-degree planar unit-edge graph on a 10-net whose construction is allowed to depend on the two chosen sources so that shortest-path distances approximate the two Euclidean distance functions.

If this is right

The Euclidean distance functions from two points admit a discrete, planar, bounded-degree approximation with uniform additive error.
The approximation is possible on any sufficiently dense point set once the sources are fixed.
Planarity and unit edge lengths do not prevent the simultaneous approximation of two distance functions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the two-source construction extends, a single planar graph could serve as a discrete proxy for multiple continuous distance-based processes.
The logarithmic obstruction for large ordered sets indicates a dimensional limit on how many independent distance functions a planar graph metric can encode at once.

Load-bearing premise

The graph may be chosen after the two sources are given and the underlying point set need only be a 10-net.

What would settle it

Three non-collinear points together with a 10-net on which no bounded-degree planar unit-edge graph makes both graph-distance functions agree with Euclidean distance up to any fixed additive constant.

Figures

Figures reproduced from arXiv: 2606.13271 by Itai Benjamini.

**Figure 2.** Figure 2: A fixed column. The clouds may increase in size as the Euclidean cells become larger. A [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

read the original abstract

We prove that two fixed sources in the Euclidean plane can be realized by a bounded-degree planar unit-edge graph on a 10-net, with graph distance from each source agreeing with Euclidean distance up to a universal additive constant. We ask whether the analogous statement holds for three non-collinear sources, and prove a logarithmic obstruction for large ordered source sets in the coordinate-planar setting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Benjamini proves a clean two-source realization result with unit-edge planar graphs on 10-nets and gives a logarithmic obstruction for ordered sets.

read the letter

The paper shows that for any two fixed points in the plane you can find a bounded-degree planar graph with unit edges on a 10-net whose hop distances from those points match Euclidean distance up to a fixed additive error. It also proves that no such construction works for large ordered source sets in the coordinate setting, with a logarithmic gap.

The two-source existence statement and the ordered-set obstruction look new. The framing as a fixed-source problem is a useful way to organize the comparison between Euclidean and graph metrics, and the claims are stated precisely enough that the logical structure is easy to follow from the abstract.

The main limitation is that the graph is allowed to depend on the choice of the two sources, and the underlying point set must be a 10-net rather than an arbitrary dense set. The three-source case is left open with no indication of whether the obstruction technique extends or whether a different construction might work. These are real restrictions on scope, but they are stated up front.

This is for people working on geometric graph theory and metric embeddings in the plane. The results are narrow but technically grounded, so the paper deserves a serious referee who can check the proofs in detail rather than a desk rejection.

Referee Report

0 major / 1 minor

Summary. The paper proves that for any two fixed sources in the Euclidean plane, there exists a bounded-degree planar unit-edge graph on a 10-net such that the graph distances from each source to points in the net agree with the corresponding Euclidean distances up to a universal additive constant. It poses the analogous question for three non-collinear sources and proves a logarithmic obstruction for large ordered source sets in the coordinate-planar setting.

Significance. If the existence proof holds, the result establishes that Euclidean distances from two sources can be approximated by graph distances under the constraints of planarity, bounded degree, and unit edges on a sufficiently dense net, with the construction permitted to depend on the sources. This provides a positive answer in the two-source case and a concrete obstruction for larger ordered sets, contributing to the study of metric approximations by geometric graphs. The explicit allowance for source-dependent constructions and 10-nets is consistent with the stated claim.

minor comments (1)

The abstract refers to a 'universal additive constant' without specifying its dependence (or independence) on the sources or the net; a brief clarification in the introduction would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary and significance assessment, which accurately reflect the manuscript's contributions on two-source approximations and the logarithmic obstruction for ordered sets. The recommendation of 'uncertain' appears to stem from the lack of explicit major comments or specific concerns about the proof; we stand ready to address any verification questions.

Circularity Check

0 steps flagged

No significant circularity; direct existence proof

full rationale

The paper states an existence result: for any two fixed sources, there exists a bounded-degree planar unit-edge graph on a 10-net such that graph distances from each source approximate Euclidean distances up to a universal additive constant. The abstract and claim explicitly permit the graph to depend on the sources and restrict to 10-nets. No equations, fitted parameters, self-definitional quantities, or load-bearing self-citations appear in the provided material. The central claim is proved directly rather than reduced to prior fitted constants or renamed empirical patterns. This is a self-contained existence argument with no internal reduction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The paper is a pure existence proof in metric geometry; no numerical parameters are fitted and no new entities are postulated beyond the standard notions of 10-net, planar unit-edge graph, and graph distance.

pith-pipeline@v0.9.1-grok · 5568 in / 1169 out tokens · 25687 ms · 2026-06-27T05:06:53.070335+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

4 extracted references · 3 canonical work pages

[1]

Matouˇ sek,Geometric Discrepancy: An Illustrated Guide, Algorithms and Combinatorics, vol

J. Matouˇ sek,Geometric Discrepancy: An Illustrated Guide, Algorithms and Combinatorics, vol. 18, Springer, 1999

1999
[2]

J. Pach, R. Pollack and J. Spencer,Graph distance and Euclidean distance on the grid, In: R. Bodendiek and R. Henn (eds.),Topics in Combinatorics and Graph Theory, Physica-Verlag HD, 1990, pp. 555–559.https://doi.org/10.1007/978-3-642-46908-4_63

work page doi:10.1007/978-3-642-46908-4_63 1990
[3]

Radin,The pinwheel tilings of the plane, Annals of Mathematics139(1994), no

C. Radin,The pinwheel tilings of the plane, Annals of Mathematics139(1994), no. 3, 661–702. https://doi.org/10.2307/2118575

work page doi:10.2307/2118575 1994
[4]

Benjamini,Euclidean vs

I. Benjamini,Euclidean vs. graph metric, In: L. Lov´ asz, I. Z. Ruzsa and V. T. S´ os (eds.),Erd˝ os Centennial, Bolyai Society Mathematical Studies, vol. 25, Springer, Berlin, Heidelberg, 2013, pp. 35–57.https://doi.org/10.1007/978-3-642-39286-3_2. 8

work page doi:10.1007/978-3-642-39286-3_2 2013

[1] [1]

Matouˇ sek,Geometric Discrepancy: An Illustrated Guide, Algorithms and Combinatorics, vol

J. Matouˇ sek,Geometric Discrepancy: An Illustrated Guide, Algorithms and Combinatorics, vol. 18, Springer, 1999

1999

[2] [2]

J. Pach, R. Pollack and J. Spencer,Graph distance and Euclidean distance on the grid, In: R. Bodendiek and R. Henn (eds.),Topics in Combinatorics and Graph Theory, Physica-Verlag HD, 1990, pp. 555–559.https://doi.org/10.1007/978-3-642-46908-4_63

work page doi:10.1007/978-3-642-46908-4_63 1990

[3] [3]

Radin,The pinwheel tilings of the plane, Annals of Mathematics139(1994), no

C. Radin,The pinwheel tilings of the plane, Annals of Mathematics139(1994), no. 3, 661–702. https://doi.org/10.2307/2118575

work page doi:10.2307/2118575 1994

[4] [4]

Benjamini,Euclidean vs

I. Benjamini,Euclidean vs. graph metric, In: L. Lov´ asz, I. Z. Ruzsa and V. T. S´ os (eds.),Erd˝ os Centennial, Bolyai Society Mathematical Studies, vol. 25, Springer, Berlin, Heidelberg, 2013, pp. 35–57.https://doi.org/10.1007/978-3-642-39286-3_2. 8

work page doi:10.1007/978-3-642-39286-3_2 2013