On the number of minimal 1-Steiner trees (Q1330879): Difference between revisions

A minimum 1-Steiner tree is a minimum spanning tree whose set of vertices consists of \(n\) given points and exactly one additional point. There is an algorithm for constructing such trees in the plane by \textit{G. Georgakopoulos} and \textit{C. H. Papadimitriu} [The 1-Steiner tree problem, J. Algorithms 8, 122-130 (1987; Zbl 0642.68131)], fixing the position of the extra vertex in at most \(O(n^ 2)\) combinatorially distinct positions and considering the minimum spanning tree of the \(n+1\) points. The paper shows that the maximum possible number of combinatorially distinct minimum 1-Steiner trees on \(n\) given points in the \(d\)- dimensional space is \(O(n^ d(\log n)^{f(d)})\), where \(f(d)= 2d^ 2- d\).