Graph metric approximating Euclidean metric

Question

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?

Answer 1

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.

Answer 2

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.