Rotational Steiner Ratio Problem Under Uniform Orientation Metrics

摘要

Let P be a set of n points in a metric space. A Steiner Minimal Tree (SMT) on P is a shortest network interconnecting P while a Minimum Spanning Tree (MST) is a shortest network interconnecting P with all edges between points of P. The Steiner ratio is the infimum over P of ratio of the length of SMT over that of MST. Steiner ratio problem is to determine the value of the ratio. In this paper we consider the Steiner ratio problem in uniform orientation metrics, which find important applications in VLSI design. Our study is based on the fact that lengths of MSTs and SMTs could be reduced through properly rotating coordinate systems without increasing the number of orientation directions. We obtain the Steiner ratios with ∣P∣ = 3 when rotation is allowed and some bounds of Steiner ratios for general case.