The Squishy Grid Problem

Zixi Cai, Kuowen Chen, Shengquan Du, Arnold Filtser, Seth Pettie, Daniel SkoraarXiv 2025 · DOI · arXiv

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.

Recursive subdivision of a pinwheel tiling triangle used to generate uniform orientations.

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.

A hierarchical path construction showing how segments L1, L2, and L3 approximate a straight line through wiggling.

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

Abstract

In this paper we consider the problem of approximating Euclidean distances by the infinite integer grid graph. Although the topology of the graph is fixed, we have control over the edge-weight assignment $w:E\to \mathbb{R}_{\ge 0}$, and hope to have grid distances be asymptotically isometric to Euclidean distances, that is, for all grid points $u,v$, $\mathrm{dist}_w(u,v) = (1\pm o(1))\|u-v\|_2$. We give three methods for solving this problem, each attractive in its own way. * Our first construction is based on an embedding of the recursive, non-periodic pinwheel tiling of Radin and Conway into the integer grid. Distances in the pinwheel graph are asymptotically isometric to Euclidean distances, but no explicit bound on the rate of convergence was known. We prove that the multiplicative distortion of the pinwheel graph is $(1+1/Θ(\log^ξ\log D))$, where $D$ is the Euclidean distance and $ξ=Θ(1)$. The pinwheel tiling approach is conceptually simple, but can be improved quantitatively. * Our second construction is based on a hierarchical arrangement of "highways." It is simple, achieving stretch $(1 + 1/Θ(D^{1/9}))$, which converges doubly exponentially faster than the pinwheel tiling approach. * The first two methods are deterministic. An even simpler approach is to sample the edge weights independently from a common distribution $\mathscr{D}$. Whether there exists a distribution $\mathscr{D}^*$ that makes grid distances Euclidean, asymptotically and in expectation, is major open problem in the theory of first passage percolation. Previous experiments show that when $\mathscr{D}$ is a Fisher distribution, grid distances are within 1\% of Euclidean. We demonstrate experimentally that this level of accuracy can be achieved by a simple 2-point distribution that assigns weights 0.41 or 4.75 with probability 44\% and 56\%, respectively.
BibTeX
@misc{cai2025squishy,
  author = {Zixi Cai and Kuowen Chen and Shengquan Du and Arnold Filtser and Seth Pettie and Daniel Skora},
  title = {{The Squishy Grid Problem}},
  year = {2025},
  eprint = {2507.23105},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.23105},
}
Figure