Bounding the expected number of rectilinear full Steiner trees

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Bounding the expected number of rectilinear full Steiner trees. / Wulff-Nilsen, Christian.

In: Networks, Vol. 56, No. 1, 2010, p. 1-10.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Wulff-Nilsen, C 2010, 'Bounding the expected number of rectilinear full Steiner trees', Networks, vol. 56, no. 1, pp. 1-10. https://doi.org/10.1002/net.20342

APA

Wulff-Nilsen, C. (2010). Bounding the expected number of rectilinear full Steiner trees. Networks, 56(1), 1-10. https://doi.org/10.1002/net.20342

Vancouver

Wulff-Nilsen C. Bounding the expected number of rectilinear full Steiner trees. Networks. 2010;56(1):1-10. https://doi.org/10.1002/net.20342

Author

Wulff-Nilsen, Christian. / Bounding the expected number of rectilinear full Steiner trees. In: Networks. 2010 ; Vol. 56, No. 1. pp. 1-10.

Bibtex

@article{c9cf25d023d011df8ed1000ea68e967b,
title = "Bounding the expected number of rectilinear full Steiner trees",
abstract = "Given a finite set Z of n points, called terminals, in d, the Rectilinear Steiner Tree Problem asks for a tree of minimal L1-length spanning Z. An optimal solution has a unique decomposition into full Steiner trees (FSTs). By using geometric properties and combinatorial arguments, we bound the expected number of FSTs satisfying simple necessary conditions for being part of an optimal solution. More specifically, we show that the expected number of FSTs spanning exactly K terminals and satisfying the empty lune property, a weak version of the bottleneck property, and the so-called empty hyperbox property is O(n(log log n)2(d-1)) for K = 3 and O(n(log log n)d-1 log K-2n) for K > 3, assuming terminals are randomly distributed in a hypercube with a uniform distribution. In the plane, we improve an earlier bound by showing that the expected number of FSTs with the Hwang form spanning exactly K terminals and satisfying the empty lune property and the so-called disjoint lunes property is O(nK). {\textcopyright} 2009 Wiley Periodicals, Inc.",
author = "Christian Wulff-Nilsen",
year = "2010",
doi = "10.1002/net.20342",
language = "English",
volume = "56",
pages = "1--10",
journal = "Networks",
issn = "0028-3045",
publisher = "JohnWiley & Sons, Inc.",
number = "1",

}

RIS

TY - JOUR

T1 - Bounding the expected number of rectilinear full Steiner trees

AU - Wulff-Nilsen, Christian

PY - 2010

Y1 - 2010

N2 - Given a finite set Z of n points, called terminals, in d, the Rectilinear Steiner Tree Problem asks for a tree of minimal L1-length spanning Z. An optimal solution has a unique decomposition into full Steiner trees (FSTs). By using geometric properties and combinatorial arguments, we bound the expected number of FSTs satisfying simple necessary conditions for being part of an optimal solution. More specifically, we show that the expected number of FSTs spanning exactly K terminals and satisfying the empty lune property, a weak version of the bottleneck property, and the so-called empty hyperbox property is O(n(log log n)2(d-1)) for K = 3 and O(n(log log n)d-1 log K-2n) for K > 3, assuming terminals are randomly distributed in a hypercube with a uniform distribution. In the plane, we improve an earlier bound by showing that the expected number of FSTs with the Hwang form spanning exactly K terminals and satisfying the empty lune property and the so-called disjoint lunes property is O(nK). © 2009 Wiley Periodicals, Inc.

AB - Given a finite set Z of n points, called terminals, in d, the Rectilinear Steiner Tree Problem asks for a tree of minimal L1-length spanning Z. An optimal solution has a unique decomposition into full Steiner trees (FSTs). By using geometric properties and combinatorial arguments, we bound the expected number of FSTs satisfying simple necessary conditions for being part of an optimal solution. More specifically, we show that the expected number of FSTs spanning exactly K terminals and satisfying the empty lune property, a weak version of the bottleneck property, and the so-called empty hyperbox property is O(n(log log n)2(d-1)) for K = 3 and O(n(log log n)d-1 log K-2n) for K > 3, assuming terminals are randomly distributed in a hypercube with a uniform distribution. In the plane, we improve an earlier bound by showing that the expected number of FSTs with the Hwang form spanning exactly K terminals and satisfying the empty lune property and the so-called disjoint lunes property is O(nK). © 2009 Wiley Periodicals, Inc.

U2 - 10.1002/net.20342

DO - 10.1002/net.20342

M3 - Journal article

VL - 56

SP - 1

EP - 10

JO - Networks

JF - Networks

SN - 0028-3045

IS - 1

ER -

ID: 18273538