The Library
Networks and Poisson line patterns : fluctuation asymptotics
Tools
Kendall, W. S. (2008) Networks and Poisson line patterns : fluctuation asymptotics. Zürich: European Mathematical Society Publishing House. (Oberwolfach Reports).
|
PDF
WRAP_Kendall_Kendall-2009b.pdf - Accepted Version - Requires a PDF viewer. Download (152Kb) |
Official URL: http://www.ems-ph.org/journals/show_issue.php?issn...
Abstract
In [1] 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.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > 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 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.5 | ||||
Number: | No.4 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 1 August 2016 | ||||
Date of first compliant Open Access: | 1 August 2016 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year