The Squishy Grid Problem

G. Tardos (personal communication) made us aware of a 1990 book chapter of Pach, Pollack, and Spencer [14] who attributed some version of Question 1 to Paul Erdős. Pach et al. [14] proved that for any fixed $ϵ>0$ there exists a graph $G[ϵ]$ on the vertex set $\mathbb{Z}\times \mathbb{Z}$ such that for all $u,v$,

Unfortunately, $G[ϵ]$ is not planar and obviously depends on $ϵ$, so it does not lead to a resolution of Question 1. Burago and Ivanov [6] exhibited a regular, weighted graph $G$ on the vertex set $\mathbb{Z}\times \mathbb{Z}$ for which

for some absolute constant $C$. However, $G$ is also not planar.

Borradaile and Eppstein [4] considered a more general problem: given a point set $P\in {ℝ}^2$, compute a weighted planar graph $G=(P\cup S,E)$ with Steiner points $S$ such that ${\mathrm{dist}}_G(u,v)$ $(1+ϵ)$-approximates the Euclidean distance ${\Vert u-v\Vert }_2$. They proved that $|S|=O_{ϵ,\alpha }(|P|)$ suffices, where $\alpha$ is the sharpest angle in the Delaunay triangulation of $P$. A result of Chang, Krauthgamer, and Tan [8] implies an upper bound of $O_{ϵ}(|P|\mathrm{polylog}|P|)$, which is slightly superlinear but independent of $\alpha$.

The problem was first posed to us by G. Bodwin, not as a deterministic design problem (Question 1) but as a randomized one. Whenever $𝒟$ is a distribution over ${ℝ}_{\ge 0}$, let $\mathrm{𝖦𝗋𝗂𝖽}[𝒟]$ be the distribution of weighted graphs such that for each $e\in E(\mathrm{𝖦𝗋𝗂𝖽})$, $w(e)\sim 𝒟$ is sampled independently from the distribution. Is it possible to find a distribution ${𝒟}^{\ast }$ such that distances in $\mathrm{𝖦𝗋𝗂𝖽}[{𝒟}^{\ast }]$ are Euclidean in expectation? In more detail:

The randomized process implicit in Question 2 is actually not new, but dates back to at least a 1965 paper of Hammersley and Welsh [11], who called it first passage percolation. They imagined an orchard in which trees were planted on the integer lattice. One tree is initially infected, and the time taken for an infected tree to infect a cardinal neighbor is governed by a distribution $𝒟$ on ${ℝ}_{\ge 0}$. One can then ask: how far does the infection spread by time $t$? and what does the set of infected trees look like?

Many basic questions in first passage percolation theory remain open, and we can quickly summarize the known facts related to Question 2. Let $\mathrm{𝟎}=(0,0)$ be the origin and $e_{\theta }$ be the unit vector with angle $\theta$ degrees. We interpret $n{e}_{\theta }$ to mean the integer point in $V(\mathrm{𝖦𝗋𝗂𝖽})$ nearest to $n{e}_{\theta }$. The time constant ${\mu }_0(𝒟)$ is such that ${lim}_{n\to \mathrm{\infty }}{\mathrm{dist}}_w(\mathrm{𝟎},n{e}_0)/n={\mu }_0$ almost surely, which exists if, whenever $w_1,\mathrm{\dots },w_4\sim 𝒟$ are independently sampled, [12]. It follows that $0\le {\mu }_0\le 𝔼(w_1\sim 𝒟)$, with the latter inequality holding with equality only if $w_1\sim 𝒟$ is constant almost surely [11]. Similarly, the time constants for other angles ${\mu }_{\theta }(𝒟)={lim}_{n\to \mathrm{\infty }}{\mathrm{dist}}_w(\mathrm{𝟎},n{e}_{\theta })/n$ exist, and collectively define the limiting shape of the balls under distribution $𝒟$. Let $B(t)=\{u\in {\mathbb{Z}}^2\mid {\mathrm{dist}}_w(\mathrm{𝟎},u)\le t\}$ be the ball of radius $t$ around the origin. The Cox-Durrett shape theorem [10] shows that with probability 1, as $t\to \mathrm{\infty }$, $B(t)/t$ tends to a fixed limit shape $ℬ(𝒟)\subset {ℝ}^2$. When ${\mu }_0(𝒟)>0$, $ℬ(𝒟)$ is bounded, convex, and has the same symmetries as ${\mathbb{Z}}^2$, and when ${\mu }_0(𝒟)=0$, $ℬ(𝒟)$ is ${ℝ}^2$ itself. See [2] for an extensive survey of first passage percolation theory.

In the context of answering Question 2 we can rescale any non-trivial distribution $𝒟$ so that its time constant ${\mu }_0(𝒟)=1$, i.e., distances from the origin to points on the $x$- and $y$-axes are asymptotically isometric. In light of the Cox-Durrett theorem, Question 2 asks whether there exists a $𝒟$ for which $ℬ(𝒟)$ is the unit $L_2$ ball $\{x\mid {\Vert x\Vert }_2\le 1\}$.

Unfortunately, there are no results characterizing $ℬ(𝒟)$ for any non-trivial distribution $𝒟$. It is not even known whether there exists $𝒟$ such that

i.e., $ℬ(𝒟)$ coincides with the unit $L_2$-ball on the eight (inter)cardinal directions. On the other hand, we have solid experimental evidence that $ℬ(𝒟)$ can get within 1% of the unit $L_2$-ball, for certain distributions $𝒟$. An experimental study of Alm and Deijfen [1] looked at various continuous distributions $𝒟$. When $𝒟$ is the uniform distribution, the limit shape $ℬ(𝒟)$ approximates the $L_2$-ball to with 4%, whereas when $𝒟$ is exponential the limit shape is about 1.5% away from the $L_2$-ball. The best empirical approximation to the $L_2$-ball came from a Fisher distribution, with error less than 1%.

We provide two approaches to answering Question 1 and present experimental evidence that Question 2 can be answered in the affirmative, using simple discrete distributions.

Our first construction is based on Radin and Conway’s pinwheel tiling [15, 16, 9], a conceptually simple tiling that emerges from the observation that a right triangle with proportions $1:2:\sqrt{5}$ can be partitioned into five right triangles with the same proportions. It is known [16] that when regarded as a plane graph $G_{\mathrm{PW}}$ with edges weighted according to Euclidean distance, distances in the pinwheel tiling are Euclidean in the limit, that is,

However the rate of convergence is unknown. We embed the pinwheel tiling into the grid graph, and prove a bound on its convergence, namely that for a constant $\xi =\mathrm{\Theta }(1)$,

A natural problem is to optimize the convergence rate of the construction. We give a new, simple construction of a weight function $w$ of the grid that is asymptotically Euclidean, with a polynomial convergence rate, namely: ${\mathrm{dist}}_w(u,v)={\Vert u-v\Vert }_2+O({\Vert u-v\Vert }_2^{8/9})$.

The construction is based on laying out “highways” in the plane, which are paths cleaving closely to a line with a certain slope $a$, whose edge weights are equal and chosen to approximate Euclidean distances along the highway. For example, when $a\in [0,1]$, the weights are $\frac{\sqrt{a^2+1}}{a+1}$. In order to get a $(1+o(1))$-distance approximation, it is necessary that the set of slopes of all highways be dense in $[0,\pi )$. Thus, there are infinitely many slopes, and infinitely many parallel highways of each slope, whose intersection pattern is quite complicated. The tricky part in the design stage is to decide what to do with intersecting highways. We give a simple method that eliminates intersections while guaranteeing polynomial convergence.

Alm and Deijfen’s [1] experimental study of first passage percolation selected $𝒟$ from various continuous distributions such as uniform, exponential, Gamma, and Fisher distributions. For several of these distributions the limit shape $ℬ(𝒟)$ approximated the $L_2$-ball within a few percent, with a Fisher distribution being the best. Our experiments show that very simple distributions with support size 2 or 3 can replicate the accuracy of the continuous distributions [1]. For example, the improbable distribution ${𝒟}_2$:

empirically approximates the Euclidean metric to within about $0.75\%$, and a certain 3-point distribution ${𝒟}_3$ approximates it to within $0.622\%$. A very natural question is whether other $L_p$ metrics can be approximated, in expectation, by various distributions. We illustrate that the uniform distribution and some Gamma distributions approximate $L_p$ metrics with . None of our experiments support the possibility that $L_p$ metrics with $p>2$ can be approximated.

We present the construction based on pinwheel tilings in Section 2, as well as new bounds on the convergence of the stretch of the pinwheel graph. The highway construction is presented in Section 3, having polynomial convergence. We present the experimental findings in Section 4 and conclude with a discussion of several open problems related to Questions 1 and 2 in Section 5. Sections 2, 3, and 4 are written to be independent.

By construction ${𝒯}_{\omega }$ is a tiling of the plane using atomic triangles with side lengths $1,2,\sqrt{5}$. Due to the recursive nature of the construction, we can also regard ${𝒯}_{\omega }$ as a tiling using ${\sqrt{5}}^i,2{\sqrt{5}}^i,{\sqrt{5}}^{i+1}$ triangles, for any integer $i\ge 0$. Observe from Figure 1 that the boundary of ${𝒯}_{i+1}$ is obtained from the boundary ${𝒯}_i$ by scaling by $\sqrt{5}$, translation, and rotation by $\arctan (1/2)$. We will henceforth define $\gamma =\arctan (1/2)$. As $\gamma /(2\pi )$ is irrational, the orientation of tiles in ${𝒯}_{\omega }$ is uniformly distributed in $[0,2\pi )$. Radin and Sadun [16] used this fact to prove an isoperimetric property of pinwheel tilings, namely that there are finite subsets of tiles from ${𝒯}_{\omega }$ whose area/perimeter² is arbitrarily close to that of the circle. Suppose we regard ${𝒯}_{\omega }$ as a plane graph $G_{\omega }$, whose vertices and edges are the union of the vertices and edges of all atomic triangles. Radin and Sadun [16] proved that for $u,v\in V(G_{\omega })$, ${\mathrm{dist}}_{G_{\omega }}(u,v)=(1+o(1)){\Vert u-v\Vert }_2$. Although the multiplicative stretch is 1 in the limit, their proof implies no particular rate of convergence. We prove the following.

If $T$ is a triangle in the recursive tiling with dimensions ${\sqrt{5}}^i,2{\sqrt{5}}^i,{\sqrt{5}}^{i+1}$, we call $T$ a level-$i$ triangle. As a first step toward proving Theorem 1, we analyze the orientations of the triangles contained within a single large triangle. Given a triangle $T$ of level $x$, let $\mathrm{Ang}(T,k)$ denote the set of angles attained by the hypotenuses of all level-$(x-k)$ triangles contained within $T$. We observe that the elements of this set are characterized by an arithmetic recurrence.

We define $f(d)$ to be the maximum stretch guaranteed by $G_{\omega }$, over all pairs of vertices at Euclidean distance at least $d$.

The proof of this theorem can be found in the full version [7].

Given a line $\mathrm{\ell }=ax+b$ in ${ℝ}^2$ we define the $\mathrm{Highway}(\mathrm{\ell })$ to be a grid-path that tracks $\mathrm{\ell }$; see Figure 3.

Specifically, let $v\in V(\mathrm{𝖦𝗋𝗂𝖽})$ be a grid-point, and consider the $1\times 1$ square $[v-0.5,v+0.5)\times [v-0.5,v+0.5)$. If $\mathrm{\ell }$ intersects this square, then we include $v$ in $V(\mathrm{\ell })$. Whenever $u,v\in V(\mathrm{\ell })$ are adjacent grid points, $\mathrm{Highway}(\mathrm{\ell })$ contains the edge $\{u,v\}\in E(\mathrm{𝖦𝗋𝗂𝖽})$. If $a\in [-1,1]$ we let $w_{\mathrm{\ell }}$ assign every edge in $\mathrm{Highway}(\mathrm{\ell })$ the weight $\frac{\sqrt{a^2+1}}{|a|+1}$, which is the asymptotic ratio between the Euclidean distance of points on $\mathrm{\ell }$ and the number of edges taken along the grid path $\mathrm{Highway}(\mathrm{\ell })$. Otherwise we write $\mathrm{\ell }$ as $x=a^{-1}(y-b)$ with $a^{-1}\in [-1,1]$ and use weight $\frac{\sqrt{a^{-2}+1}}{|a^{-1}|+1}$. All off-highway edges have weight $\mathrm{\infty }$.

This weight assignment guarantees a discrepancy of at most 1 between Euclidean distances and grid distances along $\mathrm{Highway}(\mathrm{\ell })$. The proof of Lemma 9 appears in [7].

The highway transformation can also be applied to a line segment $s$. We use the same notation $\mathrm{Highway}(s)$.

We are trying to find a weight assignment for the finite grid $[n]\times [n]$ in order to prove Theorem 8. The construction is parameterized by ${(k_i)}_{1\le i\le m}$, where $k_1=\lfloor n^{1/5}\rfloor ,k_{i+1}=\lfloor k_i^{1/2}\rfloor$, and $m$ is minimum such that .

The construction is based on a hierarchical system of lines in ${ℝ}^2$ which will eventually be embedded as highways in the grid. The lines at level $i$ have angles selected from , where ${\theta }_{i,j}=\frac{\pi \cdot j}{k_i}$. Fixing $i$ and one such angle ${\theta }_{i,j}$, there are many lines with angle ${\theta }_{i,j}$, spaced at distance $k_i^4$. For $i\in [1,m],j\in [0,k_i-1],t\in \mathbb{Z}$, define

Define $\mathrm{𝖫𝗂𝗇𝖾𝗌}[i]=\{{\mathrm{\ell }}_{i,j,t}\}$ to be the set of all lines at level $i$.

We cannot choose a weight function $W(n)$ that agrees with $w_{{\mathrm{\ell }}_{i,j,t}}$ for every line ${\mathrm{\ell }}_{i,j,t}$ due to intersections. Our solution is to avoid this issue by removing all line intersections, which introduces distortions in distances that must be bounded.

Below we define a procedure to remove parts of ${\mathrm{\ell }}_{i,j,t}$, leaving a set of line segments ${ℒ}_{i,j,t}$. Define $\mathrm{𝖲𝖾𝗀𝗆𝖾𝗇𝗍𝗌}[i]=\bigcup {ℒ}_{i,j,t}$ to be the set of all line segments at level $i$. If $O$ is an object or collection of objects, define

to be all points within distance $\delta$ of $O$. Specifically, $\mathrm{Fat}(\mathrm{\ell },\delta )$ is a strip if $\mathrm{\ell }$ is a line, and a hippodrome if $\mathrm{\ell }$ is a segment.

Once $\mathrm{𝖲𝖾𝗀𝗆𝖾𝗇𝗍𝗌}[1],\mathrm{\dots },\mathrm{𝖲𝖾𝗀𝗆𝖾𝗇𝗍𝗌}[i-1]$ are constructed, we construct $\mathrm{𝖲𝖾𝗀𝗆𝖾𝗇𝗍𝗌}[i]$ as follows. For each ${\mathrm{\ell }}_{i,j,t}\in \mathrm{𝖫𝗂𝗇𝖾𝗌}[i]$ initialize $\mathrm{\ell }\leftarrow {\mathrm{\ell }}_{i,j,t}$ and proceed to remove parts of $\mathrm{\ell }$ in Steps 1 and 2.

Step 1.

Set $\mathrm{\ell }\leftarrow \mathrm{\ell }-\mathrm{Fat}(\mathrm{𝖫𝗂𝗇𝖾𝗌}[i]-\{\mathrm{\ell }\},k_i)$, i.e., we remove every part of $\mathrm{\ell }$ within distance $k_i$ of any other line at level $i$.

Step 2.

For each segment such that $\mathrm{Fat}(s,k_i)\cap \mathrm{\ell }\ne \mathrm{\varnothing }$, let $\overline{AB}=\mathrm{Fat}(s,k_i)\cap \mathrm{\ell }$. If ${\Vert A-B\Vert }_2\ge k_i$, set $\mathrm{\ell }\leftarrow \mathrm{\ell }-\overline{AB}$. Otherwise, let $B^{\prime }\in {\mathrm{\ell }}_{i,j,t}$ be such that $\Vert A-B^{\prime }\Vert =k_i$ and $B\in \overline{A{B}^{\prime }}$, and set $\mathrm{\ell }\leftarrow \mathrm{\ell }-\overline{A{B}^{\prime }}$. See Figure 4. Define ${ℒ}_{i,j,t}=\mathrm{\ell }$, and include all line segments of ${ℒ}_{i,j,t}$ in $\mathrm{𝖲𝖾𝗀𝗆𝖾𝗇𝗍𝗌}[i]$.

The weight assignment $W(n)$ is now constructed as follows. For each line segment $s\in {\bigcup }_i\mathrm{𝖲𝖾𝗀𝗆𝖾𝗇𝗍𝗌}[i]$, let $W(n)$ agree with $w_s$ at all edges in the corresponding highway segment $\mathrm{Highway}(s)$. All edges not appearing in any line segment have weight 2.