On the number of minimal 1-Steiner trees

B. Aronov, M. Bern, D. Eppstein

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)29-34
    Number of pages6
    JournalDiscrete & Computational Geometry
    Issue number1
    StatePublished - Dec 1994

    ASJC Scopus subject areas

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


    Dive into the research topics of 'On the number of minimal 1-Steiner trees'. Together they form a unique fingerprint.

    Cite this