Networks and Poisson line patterns : fluctuation asymptotics
Kendall, Wilfrid S. (2008) Networks and Poisson line patterns : fluctuation asymptotics. Zürich: European Mathematical Society Publishing House. (Oberwolfach Reports).
WRAP_Kendall_Kendall-2009b.pdf - Accepted Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Official URL: http://www.ems-ph.org/journals/show_issue.php?issn...
In  it was shown how to construct networks connecting arbitrary configurations
xn of n cities in a square of area n which for example (i) involve only εn more total
network length than the Euclidean Steiner tree connecting all n cities, and yet (ii)
establish a network connection length between two randomly chosen cities which
is on average only O(log n) more than average Euclidean connection length [1,
Theorem 3, version (b)]. Moreover, under a certain quantitative equidistribution
condition on the city locations xn (which can be phrased either analytically or in
terms of a truncated Wasserstein coupling between a randomly chosen city and the
uniform distribution on the square), a complementary result shows that for O(n)
total connection length the average network connection length must have an excess
over the average Euclidean connection length of at least Ω(√log n) [1, Theorem
5]. The methods of proof involve stochastic geometry: in the case of the lower
bound [1, Theorem 5] the idea is to associate the uniform choice of two cities with
approximately uniform random lines, and then to use simple ideas from stereology.
In the case of the upper bound [1, Theorem 3] one augments the Euclidean Steiner
tree by a sparse Poisson line process, to obtain good long-distance communication,
and adds an additional relatively infinitesimal amount of additional connectivity,
to ensure efficient passage from Steiner tree to line process network.
|Subjects:||Q Science > QA Mathematics|
|Divisions:||Faculty of Science > Statistics|
|Library of Congress Subject Headings (LCSH):||System analysis|
|Series Name:||Oberwolfach Reports|
|Publisher:||European Mathematical Society Publishing House|
|Place of Publication:||Zürich|
|Access rights to Published version:||Restricted or Subscription Access|
 David J. Aldous and Wilfrid S. Kendall. Short-length routes in low-cost networks via Poisson
Actions (login required)