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 条
[41]   k-Steiner-minimal-trees in metric spaces [J].
Cieslik, D. .
Discrete Mathematics, 1999, 208-209 :119-124
[42]   Improved computation of optimal rectilinear Steiner minimal trees [J].
Ganley, JL ;
Cohoon, JP .
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1997, 7 (05) :457-472
[43]   The structure of minimal Steiner trees in the neighborhoods of the lunes of their edges [J].
Ivanov, A. O. ;
Sedina, O. A. ;
Tuzhilin, A. A. .
MATHEMATICAL NOTES, 2012, 91 (3-4) :339-353
[44]   HEXAGONAL COORDINATE SYSTEMS AND STEINER MINIMAL-TREES [J].
HWANG, FK ;
WENG, JF .
DISCRETE MATHEMATICS, 1986, 62 (01) :49-57
[45]   EXACT COMPUTATION OF STEINER MINIMAL-TREES IN THE PLANE [J].
COCKAYNE, EJ ;
HEWGILL, DE .
INFORMATION PROCESSING LETTERS, 1986, 22 (03) :151-156
[46]   STEINER MINIMAL-TREES ON REGULAR POLYGONS WITH CENTER [J].
WENG, JF ;
BOOTH, RS .
DISCRETE MATHEMATICS, 1995, 141 (1-3) :259-274
[47]   A NEW BOUND FOR EUCLIDEAN STEINER MINIMAL-TREES [J].
CHUNG, FRK ;
GRAHAM, RL .
ANNALS OF THE NEW YORK ACADEMY OF SCIENCES, 1985, 440 :328-346
[48]   IDENTIFYING STEINER MINIMAL TREES ON FOUR POINTS IN SPACE [J].
Weng, J. F. ;
Thomas, D. A. ;
Mareels, I. .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2009, 1 (03) :401-411
[49]   Using a Conic Formulation for Finding Steiner Minimal Trees [J].
Marcia Fampa ;
Nelson Maculan .
Numerical Algorithms, 2004, 35 :315-330
[50]   STEINER MINIMAL-TREES ON SETS OF 4 POINTS [J].
DU, DZ ;
HWANG, FK ;
SONG, GD ;
TING, GY .
DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (04) :401-414
12345