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.

翻译：本文研究通过无限整数网格图逼近欧几里得距离的问题。虽然图的拓扑结构固定，但我们可以控制边权分配$w:E\\to \\mathbb{R}_{\\ge 0}$，希望网格距离渐近等距于欧几里得距离，即对所有网格点$u,v$满足$\\mathrm{dist}_w(u,v) = (1\\pm o(1))\\|u-v\\|_2$。我们提出三种解决该问题的方法，各具特色。* 第一种构造基于将Radin和Conway提出的递归非周期性风车铺砌嵌入整数网格。风车图距离渐近等距于欧几里得距离，但收敛速率的确切界此前未知。我们证明风车图的乘性畸变为$(1+1/\\Theta(\\log^\\xi\\log D))$，其中$D$为欧几里得距离，$\\xi=\\Theta(1)$。风车铺砌方法概念简洁，但可定量改进。* 第二种构造基于'高速公路'的层次化排布。该方法简单，达到拉伸因子$(1 + 1/\\Theta(D^{1/9}))$，其收敛速度比风车铺砌方法快双指数级。* 前两种方法为确定性方法。更简单的方法是独立从共同分布$\\mathscr{D}$中采样边权。是否存在分布$\\mathscr{D}^*$能使网格距离在渐近意义和期望意义上等于欧几里得距离，是首通渗流理论中的重大开放问题。先前实验表明，当$\\mathscr{D}$为Fisher分布时，网格距离与欧几里得距离误差在1%以内。我们通过实验证明，采用简单的两点分布（以44%和56%概率分别赋予权重0.41和4.75）即可达到此精度水平。