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 条
[21]   Steiner minimal trees for a class of zigzag lines [J].
Booth, R.S. ;
Weng, J.F. .
Algorithmica (New York), 1992, 7 (2-3) :231-246
[22]   Improved computation of plane Steiner Minimal Trees [J].
Cockayne, E.J. ;
Hewgill, D.E. .
Algorithmica (New York), 1992, 7 (2-3) :219-229
[23]   ON FINDING RECTILINEAR STEINER MINIMAL-TREES [J].
BASART, JM ;
RIFA, J .
REVISTA DE INFORMATICA Y AUTOMATICA, 1989, 22 (02) :40-45
[24]   Steiner Minimal Trees in rectilinear and octilinear planes [J].
Shang, Song Pu ;
Jing, Tong .
ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2007, 23 (09) :1577-1586
[25]   Steiner minimal trees in Lp2 [J].
Discrete Math, 1-3 (39)
[26]   Minimal Steiner trees in X architecture with obstacles [J].
Luo, CC ;
Hwang, YS ;
Jan, GE .
CDES '05: PROCEEDINGS OF THE 2005 INTERNATIONAL CONFERENCE ON COMPUTER DESIGN, 2005, :198-203
[27]   EUCLIDEAN STEINER MINIMAL-TREES WITH OBSTACLES AND STEINER VISIBILITY GRAPHS [J].
WINTER, P .
DISCRETE APPLIED MATHEMATICS, 1993, 47 (02) :187-206
[28]   Steiner Minimal Trees with One Polygonal Obstacle [J].
J. F. Weng ;
J. MacGregor Smith .
Algorithmica, 2001, 29 :638-648
[29]   A CLASS OF FULL STEINER MINIMAL-TREES [J].
HWANG, FK ;
WENG, JF ;
DU, DZ .
DISCRETE MATHEMATICS, 1983, 45 (01) :107-112
[30]   Steiner minimal trees with one polygonal obstacle [J].
Weng, JF ;
Smith, JM .
ALGORITHMICA, 2001, 29 (04) :638-648
12345