标题： 柔软网格问题 显示英文标题

标题： The Squishy Grid Problem

摘要： 在本文中，我们考虑通过无限整数网格图来近似欧几里得距离的问题。 尽管图的拓扑结构是固定的，但我们对边权分配$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。 显示英文摘要

摘要： 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/\Theta(\log^\xi \log D))$, where $D$ is the Euclidean distance and $\xi=\Theta(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/\Theta(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.