ON THE NUMBER OF MINIMAL-1-STEINER TREES

被引：1
作者：
ARONOV, B
BERN, M
EPPSTEIN, D
机构：
[1] XEROX CORP,PALO ALTO RES CTR,PALO ALTO,CA 94304
[2] UNIV CALIF IRVINE,DEPT INFORMAT & COMP SCI,IRVINE,CA 92717
来源：
DISCRETE & COMPUTATIONAL GEOMETRY | 1994年 / 12卷 / 01期
关键词：
D O I：
10.1007/BF02574363
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We count the number of nonisomorphic geometric minimum spanning trees formed by adding a single point to an n-point set in d-dimensional space, by relating it to a family of convex decompositions of space. The O(n(d)log(2d2-d)n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor.
引用
收藏
页码：29 / 34
页数：6
相关论文
共 50 条
[31]   STEINER MINIMAL TREES FOR ZIGZAG LINES WITH LADDERS [J].
He Yong Yang QifanDeptofMathZhejiangUnivHangzhou .
AppliedMathematics:AJournalofChineseUniversities, 2001, (02) :178-184
[32]   Steiner minimal trees for zigzag lines with ladders [J].
He Y. ;
Yang Q. .
Applied Mathematics-A Journal of Chinese Universities, 2001, 16 (2) :178-184
[33]   Absorbing Angles, Steiner Minimal Trees, and Antipodality [J].
Martini, H. ;
Swanepoel, K. J. ;
de Wet, P. Oloff .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2009, 143 (01) :149-157
[34]   STEINER MINIMAL-TREES FOR REGULAR POLYGONS [J].
DU, DZ ;
HWANG, FK ;
WENG, JF .
DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (01) :65-84
[35]   Full minimal Steiner trees on lattice sets [J].
Brazil, M ;
Rubinstein, JH ;
Thomas, DA ;
Weng, JF ;
Wormald, NC .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1997, 78 (01) :51-91
[36]   Steiner Minimal Trees in Rectilinear and Octilinear Planes [J].
Song Pu Shang ;
Tong Jing .
Acta Mathematica Sinica, English Series, 2007, 23 :1577-1586
[37]   PARAMETERIZED APPROXIMATION SCHEMES FOR STEINER TREES WITH SMALL NUMBER OF STEINER VERTICES [J].
Dvorak, Pavel ;
Feldmann, Andreas E. ;
Knop, Dusan ;
Masarik, Tomas ;
Toufar, Tomas ;
Vesely, Pavel .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (01) :546-574
[38]   Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices [J].
Dvorak, Pavel ;
Feldmann, Andreas Emil ;
Knop, Dusan ;
Masarik, Tomas ;
Toufar, Tomas ;
Vesely, Pavel .
35TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2018), 2018, 96
[39]   Uniqueness of Steiner minimal trees on boundaries in general position [J].
Ivanov, A. O. ;
Tuzhilin, A. A. .
SBORNIK MATHEMATICS, 2006, 197 (9-10) :1309-1340
[40]   STEINER MINIMAL-TREES FOR A CLASS OF ZIGZAG LINES [J].
BOOTH, RS ;
WENG, JF .
ALGORITHMICA, 1992, 7 (2-3) :231-246
12345