Short-length routes in low-cost networks via Poisson line patterns
Short-length routes in low-cost networks via Poisson line patterns
复制标题
通过泊松线模式实现低成本网络中的短距离路由
DOI：
--
复制
发表时间：
2007
影响因子：
1.2
通讯作者：
W. Kendall
中科院分区：
文献类型：
--
作者：
D. Aldous;W. Kendall
在设计一个连接 n 个区域内的 n 个点的网络时，我们可能会受到以下两个需求的指导。首先，网络总长度不应远大于连接所有点的最短网络的长度。其次，平均路线长度（以源-目的地对为例）不应远大于平均直线距离。我们可以将这两种过度行为减少到多小？宽松地说，对于非简并配置，总网络长度必须至少为 n 阶，平均直线距离必须至少为 n 1/2 阶，因此可能存在超过第一个最小值为 o(n) 且超过第二个最小值为 o(n 1/2) 的单个网络似乎难以置信。但实际上我们可以做得更好：对于任意配置，我们可以构建一个网络，其中第一个超出量为 o(n)，第二个超出量几乎与 O(log n) 一样小。该构造在概念上很简单，并使用随机方法：在最小长度连接网络（斯坦纳树）上叠加稀疏平稳且各向同性的泊松线过程。加上一些添加（出于技术原因需要），所得随机网络的多余平均值满足上述渐近性；因此，概率方法的标准应用保证了所需的确定性网络的存在（建设性地说，可以使用简单的拒绝采样来构建此类网络）。关键成分是关于泊松线过程的新结果。考虑相距 r 的两个点，并从线处理中删除分隔这两个点的所有线。由此产生的线条图案将平面划分为多个单元；包含两个点的像元的平均边界长度大约等于 2r + 常数(log r)。转向下界，考虑满足弱均分布假设的网络序列。我们证明，如果第一个超出是 O(n)，那么第二个超出不能是
In designing a network to link n points in a square of area n, we might be guided by the following two desiderata. First, the total network length should not be much greater than the length of the shortest network connecting all points. Second, the average route length (taken over source-destination pairs) should not be much greater than the average straight-line distance. How small can we make these two excesses? Speaking loosely, for a nondegenerate configuration, the total network length must be at least of order n and the average straight-line distance must be at least of order n 1/2, so it seems implausible that a single network might exist in which the excess over the first minimum is o(n) and the excess over the second minimum is o(n 1/2). But in fact we can do better: for an arbitrary configuration, we can construct a network where the first excess is o(n) and the second excess is almost as small as O(log n). The construction is conceptually simple and uses stochastic methods: over the minimum-length connected network (Steiner tree) superimpose a sparse stationary and isotropic Poisson line process. Together with a few additions (required for technical reasons), the mean values of the excess for the resulting random network satisfy the above asymptotics; hence, a standard application of the probabilistic method guarantees the existence of deterministic networks as required (speaking constructively, such networks can be constructed using simple rejection sampling). The key ingredient is a new result about the Poisson line process. Consider two points a distance r apart, and delete from the line process all lines which separate these two points. The resulting pattern of lines partitions the plane into cells; the cell containing the two points has mean boundary length approximately equal to 2r + constant(log r). Turning to lower bounds, consider a sequence of networks in satisfying a weak equidistribution assumption. We show that if the first excess is O(n) then the second excess cannot be