Two Steiner Ratio Problems Considering Rotation

Xiao-Dong Hu and Song-Pu Shang
Institute of Applied Mathematics, Chinese Academy of Sciences,
P.O.Box 2734, Beijing 100080, P.R. China

Abstract

We present two new Steiner ratio problems in the plane where the orientation of the edge segments are restricted to uniformly distributed orientations, =2, 3, 4,..., and where the coordinate system could be rotated around the origin by an arbitrary angle. The most important cases with applications in VLSI design arise when =2 or =4, the so-called rectilinear case or octilinear case. As the coordinate system is rotated, the length and indeed the topology of the minimum spanning or Steiner tree changes. The known Steiner ratio is the greatest lower bound of the ratio of the length of the minimum Steiner tree (SMT) over the minimum spanning tree(MST). For one variant we suggested, both SMT and MST are minimum under rotation; for the other, the greatest lower bound is maximum under rotation. We define these two variants of Steiner ratio, and compare these three ratios. Also, we give exact value on 3 points for =2, 3, 4. We give the exact value of the first ratio for =6m and upper-bound for general .