Worst-case minimum rectilinear Steiner trees in all dimensions (Q1192611)

In this paper the distance between two points \(x=(x_ 1,\ldots,x_ d)\) and \(y=(y_ 1,\ldots,y_ d)\) of \([0,1]^ d\) in the Manhattan metric is \(d_ R(x,y)=| x_ 1-y_ 1 |+\cdots+| x_ d-y_ d |\). For \(S\subseteq[0,1]^ d\) let \(L(S)\) be the minimum length of a Steiner tree in the Manhattan metric. Then \(s^*(n)=\max \bigl\{ L(S):S \subseteq [0,1]^ d,\;| S |=n \bigr\}\) is the ``worst-case length of a minimum rectilinear Steiner tree'' of \(n\) points in the unit cube. The following nice results are proved. Let \(d \geq 2\). (1) There exists some constant \(\beta_ d>0\) such that \(s^*(n)\sim \beta_ dn^{(d-1)/d}\) \((d \geq 2,\;n \to \infty)\). (2) \(1 \leq \beta_ d \leq d4^{(1-d)/d}\). The paper gives a useful historical account and generalizes methods of \textit{F. R. K. Chung} and \textit{R. L. Graham} [Geom. Dedicata 11, No. 3, 353-361 (1981; Zbl 0475.05023)]. The exact determination of \(\beta_ d\), \(d \geq 3\), remains as an open problem.