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]   Absorbing Angles, Steiner Minimal Trees, and Antipodality [J].
H. Martini ;
K. J. Swanepoel ;
P. Oloff de Wet .
Journal of Optimization Theory and Applications, 2009, 143 :149-157
[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 Lp2 [J].
Discrete Math, 1-3 (39)
[25]   Steiner Minimal Trees in rectilinear and octilinear planes [J].
Shang, Song Pu ;
Jing, Tong .
ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2007, 23 (09) :1577-1586
[26]   EUCLIDEAN STEINER MINIMAL-TREES WITH OBSTACLES AND STEINER VISIBILITY GRAPHS [J].
WINTER, P .
DISCRETE APPLIED MATHEMATICS, 1993, 47 (02) :187-206
[27]   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
[28]   STEINER MINIMAL TREES FOR ZIGZAG LINES WITH LADDERS [J].
He Yong Yang QifanDept.ofMath. .
AppliedMathematics:AJournalofChineseUniversities, 2001, (02) :178-184
[29]   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
[30]   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
12345