Worst-case minimum rectilinear steiner trees in all dimensions

It is proved that the length of the longest possible minimum rectilinear Steiner tree ofn points in the unitd-cube is asymptotic toβ _dn^(d−1)/d , whereβ _d is a constant that depends on the dimensiond≥2. A method of Chung and Graham (1981) is generalized to dimensiond to show that 1≤β _d≤d4^(1−d)/d . In addition to replicating Chung and Graham's exact determination ofβ ₂=1, this generalization yields new bounds such as 1≤β ₃<1.191 and .