On the number of minimal 1-Steiner trees

B. Aronov; M. Bern; D. Eppstein

doi:10.1007/BF02574363

On the number of minimal 1-Steiner trees

B. Aronov, M. Bern, D. Eppstein

Research output: Contribution to journal › Article › peer-review

Abstract

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^{2 d 2}-d n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor.

Original language	English (US)
Pages (from-to)	29-34
Number of pages	6
Journal	Discrete & Computational Geometry
Volume	12
Issue number	1
DOIs	https://doi.org/10.1007/BF02574363
State	Published - Dec 1994

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/BF02574363

Cite this

@article{ac789c95dcaa4bef8348c3c14571b994,

title = "On the number of minimal 1-Steiner trees",

abstract = "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 log2 d 2-d n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor.",

author = "B. Aronov and M. Bern and D. Eppstein",

year = "1994",

month = dec,

doi = "10.1007/BF02574363",

language = "English (US)",

volume = "12",

pages = "29--34",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - On the number of minimal 1-Steiner trees

AU - Aronov, B.

AU - Bern, M.

AU - Eppstein, D.

PY - 1994/12

Y1 - 1994/12

N2 - 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 log2 d 2-d n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor.

AB - 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 log2 d 2-d n) bound that we obtain significantly improves previously known bounds and is tight to within a polylogarithmic factor.

UR - http://www.scopus.com/inward/record.url?scp=51649137047&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51649137047&partnerID=8YFLogxK

U2 - 10.1007/BF02574363

DO - 10.1007/BF02574363

M3 - Article

AN - SCOPUS:51649137047

SN - 0179-5376

VL - 12

SP - 29

EP - 34

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

On the number of minimal 1-Steiner trees

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this