On the Exact Location of Steiner Points in General Dimension

The Steiner Problem is to form a minimum-length tree that contains a given set of points, where augmentation of the point set with additional (Steiner) points is permitted. The Rectilinear Steiner Problem is one in which edge weights are determined by the L₁, or Manhattan, distance between points in Rᵈ. Let S be a set of n points Rᵈ, where d ≥ 2. By generalizing a planar theorem of Hanan (SIAM J. Appl. Math., 14 (1966), pp. 255–265.) to all dimensions, a set of O(nᵈ ) points that is guaranteed to include all the Steiner points of a minimum rectilinear Steiner tree of S is constructed, complementing Hanan’s result in $d = 2$. The theorem here and its proof illuminate new combinatorial and geometrical facts about rectilinear Steiner trees; one immediate benefit is algorithms that are asymptotically faster than all known algorithms for the problem in dimensions three and greater. The theorem also yields a polynomial algorithm in all dimensions for a version of the problem known as the Rectilinear k-Steiner Problem.