Source-linked AI summary
Euclidean vs Graph Metric: The Fixed-Source Problem
Itai Benjamini
TL;DR
The paper asks whether fixed-source Euclidean distances can be represented by bounded-degree planar graphs, proves this for two sources, and identifies a logarithmic obstruction for large ordered source sets. It leaves the case of three non-collinear sources open.
Problem
The paper asks whether a bounded-degree planar graph on a 10-net can preserve Euclidean distances from fixed sources up to a universal additive constant.
Method
The two-source construction uses confocal coordinates, thickened confocal cells, vertex clouds, and noncrossing monotone ladders with bounded degree.
Results
Two sources admit the required construction, while large ordered source families incur an additive constant C satisfying C ≥ c log k.
Takeaways & Limitations
The result establishes a universal two-source theorem and rules out a uniform bounded-additive theorem for arbitrary finite source sets in the relevant coordinate-planar settings.
Takeaways & Limitations
The logarithmic obstruction does not address the fixed case of three non-collinear sources, and the two-source linearization has no analogous three-source form.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks whether fixed-source Euclidean distances can be approximated by a bounded-degree planar graph on a 10-net, and proves this for two sources using confocal coordinates.
- The fixed-source problem seeks a bounded-degree planar graph on a 10-net containing the sources, with graph distances approximating Euclidean distances.
- The paper also records an obstruction for arbitrary finite source sets in coordinate-planar settings, already for large ordered families.
- Two sources are realizable with universal additive error for every graph vertex.
- The construction uses a thickened confocal grid whose cells contain vertex clouds connected by noncrossing monotone ladders.
2 Confocal coordinates
Confocal coordinates linearize the two Euclidean distance functions, allowing the plane to be organized into cells indexed by two coordinates.
- After translation and rotation, the construction assumes a large integer source separation D, with bounded and non-integral cases handled separately.
- The coordinate relations |x −p| = t(x) + h(x) and |x −q| = D −t(x) + h(x) make both distance functions linear in (t, h).
- Curves h = constant are confocal ellipses, while curves t = constant are confocal hyperbolas.
- Figure 1 depicts the confocal coordinate grid for p and q, which is thickened to build the graph.
- The (t, h) half-strip is divided into unit rectangles R_i,j, whose images form upper and lower confocal cells except on h = 0.
3 How the short graph paths look
Approximate shortest paths to a vertex in a confocal cell first move horizontally to its column and then vertically through that column.
- A path from p to a vertex in cell (i, j) has horizontal motion along the bottom row followed by vertical motion in fixed column i.
- The two phases use about i and j steps, so the total path length is about i + j, matching the distance expression.
- Clouds may grow with height because larger Euclidean cells require more vertices to preserve the 10-net property.
- Figure 2 illustrates a fixed column, expanding clouds, noncrossing ladders, and a path from p to a top-cloud vertex.
4 The combinatorial ladders
Ordered ladders connect neighboring clouds without crossings while ensuring coverage and uniformly bounded degree.
- The ordered-ladder lemma connects two finite linearly ordered sets placed on opposite sides of a rectangle.
- The resulting noncrossing bipartite graph gives every vertex a neighbor and has degree bounded by a constant depending only on C0.
- The construction connects ordered elements when their associated subintervals intersect, making edges order-preserving and noncrossing.
5 Clouds in the confocal cells
The construction places carefully sized vertex clouds in confocal cells and connects them with ordered, noncrossing ladders to obtain a planar bounded-degree 10-net.
- Geometry: Confocal coordinates provide the parametrization underlying the cell decomposition and comparison of neighboring cell geometry.The metric coefficients have integrable endpoint singularities, making adjacent image cells comparable in side lengths, areas, and covering requirements.
- Ladder construction: Clouds are ordered along the sides where they connect, allowing ladders to preserve order without crossings.Bottom-row cells reserve separate corridors when horizontal and vertical connections coexist.
- Planarity and degree: Comparable adjacent cloud sizes make every ladder uniformly bounded-degree, while disjoint corridors make the combined drawing planar.The predecessor property ensures every vertex in a following cloud can be reached from the preceding cloud.
- Cloud placement: Each cell receives a finite cloud that is 5-dense, has size comparable to its radius-2 covering number, and contributes to a 10-net.Adjacent cells have comparable covering numbers, so their clouds have comparable cardinalities.
6 Proof of the theorem
The proof assigns coordinate-based labels to vertices, derives lower bounds from how edges change those labels, and matches them with ladder-based paths from both sources.
- Distance labels: Vertices in cell (i, j) receive labels whose sums encode their approximate Euclidean distances from p and q.For every vertex x, |x −p| = A + O(1) and |x −q| = B + O(1).
- Lower bounds: Each edge changes both labels by at most one, yielding lower bounds A −O(1) and B −O(1) on paths from p and q.The argument uses the fact that edges move between consecutive cells horizontally or vertically.
- Upper bounds from p: The predecessor property lets paths from p reach the first-row cloud in column i and then climb to level j in i + j + O(1) steps.This equals A + O(1), matching the Euclidean-distance estimate from p.
- Upper bounds from q: Starting from q on the opposite side of the bottom row gives the analogous upper bound for every vertex in cell (i, j).Combining the source-specific bounds completes the distance estimates for the theorem.
- Parameter cases: Non-integral or bounded focal separation is handled by rounding and merging a final column, or by reducing to a one-source radial construction.These modifications change only universal additive constants.
7 The next fixed-source question
The two-source proof relies on a special two-coordinate linearization that does not extend to three non-collinear sources, motivating broader fixed-source questions.
- Limitation: The construction works because distances from p and q become linear in the two confocal coordinates (t, h).This linearization is identified as the special feature of the two-source argument.
- Three sources: No analogous two-coordinate linearization exists for three non-collinear sources.Whether a bounded-degree planar graph on a 10-net can approximate all three source distances remains posed as Question 1.
- Generalization: More generally, the paper asks which finite source sets admit bounded-additive approximation of all source-distance functions on a bounded-degree planar net graph.The question extends beyond the three-source case to arbitrary finite S ⊂R2.
8 Many ordered sources: a logarithmic obstruction
The paper proves a logarithmic additive-error obstruction for arbitrarily large ordered source sets under a planar-order condition, using Monge rectangle discrepancy. Thus no uniform bounded-additive theorem holds in those settings, though the fixed three-source case remains open.
- Scope: The result rules out a uniform positive answer for all finite source sets in planar embeddings enforcing Monge order, but does not address three fixed non-collinear sources.The obstruction therefore applies to large ordered families rather than settling the three-source question.
- Planar order and Monge structure: The planar order property follows when specified shortest paths meet, because swapping their tails yields the Monge inequality for D(i, j) = dG(ai, bj).In coordinate-planar settings, crossed boundary order and geodesics contained in the rectangle provide an example.
- Theorem 2: Theorem 2 gives arbitrarily large source sets S of size k for which every qualifying graph must satisfy C ≥ c log k.The graphs are unit-edge, planar, contain S as vertices, and satisfy the specified planar-order hypothesis.
- Source construction: The obstruction uses two ordered families of L = ⌊N2/3⌋ sources, with ai = (0, i) and bj = (N, N + j), so k = 2L.The construction compares graph distances with the Euclidean distance matrix on this L × L index square.
- Discrepancy argument: The mixed differences µ of the graph-distance matrix form a nonnegative integer measure, while the Euclidean mixed differences µE have size comparable to 1/N throughout the square.Rectangle sums telescope to corner values, and the additive approximation D = E + O(C) bounds the resulting rectangle discrepancy by O(C + 1).
- Discrepancy argument: Schmidt’s rectangle-discrepancy lower bound gives C + 1 ≥ c′ log(N1/3), which becomes C ≥ c log k because k = 2L ≍ N2/3.The lower bound converts the Euclidean mixed-difference scale and Monge integrality into logarithmic additive error.