Abstract
The "Squishy Grid Problem" explores whether an infinite integer grid can be modified with edge weights to approximate Euclidean distances. This paper presents two deterministic constructions—one utilizing non-periodic pinwheel tilings and another employing a hierarchical highway system—alongside a probabilistic approach using random weight distributions. The results demonstrate that these methods can achieve asymptotic isometry to Euclidean space, with deterministic bounds and empirical errors under 1%.
Introduction
In a standard integer grid with unit weights, the distance between two points is defined by the $L_1$ (Manhattan) metric. Even with the addition of diagonal edges, the resulting metric remains "blocky" and fails to match the straight-line Euclidean distance ($L_2$) characteristic of physical space.
The authors investigate the Squishy Grid Problem: Is there a way to assign non-negative weights $w$ to the edges of a standard grid such that the graph distance between any two points $u$ and $v$ is asymptotically isometric to their Euclidean distance? Specifically, as the distance between points increases, the ratio of grid distance to Euclidean distance should approach 1. This inquiry has significant implications for metric embeddings, spanners, and First Passage Percolation (FPP).
Methods
The paper presents three distinct approaches to "squishing" the grid:
1. Pinwheel Tilings (Deterministic)
This approach embeds the "pinwheel tiling" (developed by Radin and Conway) into the grid. The tiling utilizes a single right triangle with proportions 1:2:$\sqrt{5}$ that can be recursively subdivided. Because the orientations of these triangles are uniformly distributed across the plane, the resulting graph distances eventually smooth out into Euclidean distances.
2. Hierarchical Highways (Deterministic)
This method constructs "highways" (grid paths) that track lines of various slopes. To manage the complex intersections where highways cross, the authors developed a hierarchical "cleaning" procedure. This procedure removes segments near intersections while maintaining a path that remains extremely close to the ideal Euclidean line.
3. Randomized Weights (Probabilistic)
Instead of a rigid design, this method assigns edge weights randomly from a distribution $\mathcal{D}$, connecting the problem to FPP. Experimental simulations were used to identify simple discrete distributions that effectively mimic Euclidean space.
Key Insights and Ideas
The Necessity of "Wiggling"
To approximate Euclidean distance on a grid, paths cannot be "monotone" (moving only North and East). The authors demonstrate that monotone paths produce a non-convex limit shape, which can never be a Euclidean ball. Consequently, the shortest path must be allowed to "wiggle" or backtrack slightly to achieve Euclidean distances.
Convergence and Simplicity
- Convergence Trade-off: While the Pinwheel approach is conceptually elegant, it converges slowly (log-logarithmic rate). The Highway approach is more efficient, achieving a polynomial convergence rate ($D^{-1/9}$).
- Simplicity of Randomness: Surprisingly, a simple 2-point distribution (weights of 0.41 or 4.75 with specific probabilities) approximates Euclidean distance within 0.75% error, outperforming many complex continuous distributions.
Key Results
- Deterministic Guarantee: The Highway construction proves that for any two points at distance $D$, the grid distance is $D + O(D^{8/9})$.
- Pinwheel Bound: The authors established the first explicit bound on the rate of convergence for pinwheel tilings: $1 + O(1/(\log \log D)^\xi)$.
- Experimental Accuracy: A 2-point distribution achieves 0.75% error, while a 3-point distribution further reduces this to 0.622%.
Limitations and Future Work
The authors conjecture that achieving a "constant" additive error (e.g., $Dist = Euclidean + C$) may be impossible, suggesting the error must grow with distance. Furthermore, while empirical evidence for an exact Euclidean distribution in FPP is strong, a formal proof remains an open challenge. Future research will also look toward extending these hierarchical and tiling constructions to 3D grids.
Summary updated