Premium
Bounding the expected number of rectilinear full Steiner trees
Author(s) -
WulffNilsen Christian
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20342
Subject(s) - combinatorics , spanning tree , bounding overwatch , steiner tree problem , hypercube , disjoint sets , upper and lower bounds , mathematics , bottleneck , tree (set theory) , discrete mathematics , computer science , mathematical analysis , artificial intelligence , embedded system
Abstract Given a finite set Z of n points, called terminals, in ℝ d , the Rectilinear Steiner Tree Problem asks for a tree of minimal L 1 ‐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 −2 n ) 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 ( n π K ). © 2009 Wiley Periodicals, Inc. NETWORKS, 2010