The k-Steiner ratio in the rectilinear plane

A Steiner minimum tree (SMT) in the rectilinear plane is the shortest length tree interconnecting a set of points, called the regular points, possibly using additional vertices. Ak-size Steiner minimum tree (kSMT) is one that can be split into components where all regular points are leaves and all components have at mostkleaves. Thek-Steiner ratio in the rectilinear plane, ρk, is the infimum of the ratios SMT/kSMT over all finite sets of regular points. Thek-Steiner ratio is used to determine the performance ratio of several recent polynomial-time approximations for Steiner minimum trees. Previously it was known that in the rectilinear plane, ρ2=2/3, ρ3=4/5, and (2k−2)/(2k−1)≤ρk(L1)≤(2k−1)/(2k) fork≥4. In 1991, P. Berman and V. Ramaiyer conjectured that in fact ρk=(2k−1)/(2k) fork≥4. In this paper we prove their conjecture.