# Graph metric approximating Euclidean metric

I've been reading Wolfram's recent articles about graph/mesh/grid structures as an analogy for physical space, and it seems to me that there will be a problem getting the notion of distance to work out, since the natural metric on eg a square grid or triangle grid is L1, even in the limit of a very dense grid becoming a patch of the plane.

Is there any simple rule for generating a mesh-like graph that, with the length of all edges considered to the be the same, in the limit of very fine scale, closely approximates Euclidean distance in the plane?

Looking around, I was able to find this paper (https://projecteuclid.org/download/pdf_1/euclid.cmp/1104286245) which shows that if you allow the length of each edge in the graph to match its actual length in the plane, there is a solution with a simple production rule, but is it possible with all graph edges considered to be the same length?

• I really have no expertise to answer this, so I just state my intuition. I would say an appropriate infinite random graph model in which neighborhoods grow polynomially (say, with power $n-1$) feels like a good way to model $n$-dimensional Euclidean space, since there is no preference of any direction over another. – M. Winter Apr 27 at 7:35
• I think actually just solved this on square grids using a kind of family of supergraphs! I've been trying to find out if it's already been done and landed here in my search. I hope to publish the results this December 2020. PLEASE Email me, tterlep at purdue d0t edu, I'd really appreciate some feedback as this result came as somewhat of a surprise from working on simple Go Board problems! – tterlep 2 days ago
• @BenCrowell Why do you say that? – user76284 2 days ago
• Some useful references are: Pach, J., Pollack, R. and Spencer, J., 1990. Graph distance and Euclidean distance on the grid. In Topics in combinatorics and graph theory (pp. 555-559); Burago, D. and Ivanov, S., 2015. Uniform approximation of metrics by graphs. Proc. Amer. Math. Soc. 143 (2015), 1241-1256; Benjamini, I., 2013. Euclidean vs. graph metric. In Erdős Centennial (pp. 35-57). – Timothy Budd 2 days ago

Pick some small $$\epsilon>0$$, take the dilated integer lattice $$\epsilon^2\cdot\mathbb{Z}^2$$ to be our vertex set, and draw an edge between two vertices if their Euclidean distance is between $$\epsilon-2\epsilon^2$$ and $$\epsilon+2\epsilon^2$$. Let $$d(u,v)$$ denote the distance between $$u$$ and $$v$$ in this graph. Given the scaling, we might expect $$\|u-v\|_2\approx \epsilon d(u,v)$$.

We claim that every $$u,v\in \epsilon^2\cdot\mathbb{Z}^2$$ satisfies

$$\epsilon d(u,v)-2\epsilon \leq \|u-v\|_2\leq (1+2\epsilon)\cdot \epsilon d(u,v).$$

The right-hand inequality follows from the triangle inequality. For the left-hand inequality, let $$k$$ denote the smallest number of steps of length $$\epsilon$$ it takes to traverse from $$u$$ to $$v$$ in $$\mathbb{R}^2$$. For example, if $$\|u-v\|_2\leq 2\epsilon$$, then $$k=2$$. In general, $$k\leq\|u-v\|_2/\epsilon+2$$. Now take $$u_0,\ldots,u_k\in\mathbb{R}^2$$ such that $$u_0=u$$, $$u_k=v$$ and $$\|u_{i+1}-u_i\|_2=\epsilon$$ for each $$i$$. Then rounding each $$u_i$$ to the nearest point in $$\epsilon^2\cdot\mathbb{Z}^2$$ gives a path in our graph of length $$k$$. The claim follows.

• The OP didn't give any precise statement of what properties they wanted their approximation to have. At distances less than $\epsilon$, this metric is actually much worse than the taxicab metric. For example, when $\epsilon=0.1$, and we take chessboard-neighbor points, the approximate distance $\epsilon d=0.2$ has a 2000% error compared to the Euclidean distance. For taxicab geometry, the error never gets worse than about $41$%. Your model is like "freeway geometry," as if I live in LA and am required to get on the freeway for every trip, even if I just want to go to my neighbor's house. – Ben Crowell Apr 27 at 14:38
• @BenCrowell: "in the limit of very fine scale" seems precise enough, at least to discourage discussion of distances less than $\epsilon$. And yet, I'm not sure the taxicab metric fares well apples-to-apples. As in this answer, suppose you connect two points in the plane if they are taxicab distance $\epsilon$ apart. If you only consider the same grid of points $\epsilon^2 \mathbb{Z}^2$ as in this answer, then your "chessboard-neighbor points" aren't even connected! (The graph is bipartite.) Allowing all points of the plane as potential intermediate stops, you also get "2000% error". – aorq Apr 27 at 16:06
• @aorq: I've added a note in my own answer explaining why, given the OP's motivation, it's desirable to have short-range behavior that's not too pathological. – Ben Crowell Apr 27 at 16:53

Take $$M=\mathbb{R}^2\times[0,h]^k$$ for fixed $$k\ge0$$ and $$h\gtrsim 1$$. Spatter $$M$$ with dots according to a uniform probability distribution with unit density. Form a graph by connecting each dot with its $$2(2+k)$$ nearest neighbors. There will be topologically disconnected pieces of the graph, which should be finite in size. Cut these out, leaving some defects like Swiss cheese holes. If $$k$$ and $$h$$ are large, then the size and frequency of these holes is small. We can make a model with $$k=0$$, but larger $$k$$ should greatly reduce the prevalence of these holes. If we like, we can restrict our attention to some large defect-free disk in $$\mathbb{R}^2$$, or we can just live with the holes and make an infinite model.

Let $$\ell$$ be the number of steps between points on the graph, and $$r$$ the Euclidean distance in $$\mathbb{R}^2$$, ignoring the extra $$k$$ dimensions. Then I conjecture that there is some constant $$\alpha$$ such that at large distances, the relative expected error $$E(\alpha\ell-r)/r$$ approaches zero. Let $$d=\alpha\ell$$.

This model has the advantage that $$E(d-r)$$ is manifestly invariant under rotation and translation in $$\mathbb{R}^2$$. The model also degrades gracefully at small scales. At $$r\lesssim h$$, it begins to act like $$\mathbb{R}^{2+k}$$, balls have a reasonable topology, and the triangle inequality is still some kind of reasonable approximation. This reasonable behavior at small scales is a good property to have because the OP says the motivation for the question was Wolfram's ideas, in which the laws of physics operate on a spacetime grid, as in Conway's game of life. In that kind of system, the laws of physics operate between a point and its neighbors. Therefore it would be undesirable to have too pathological a geometry at short scales.