Steiner trees in general nonuniform orientations

In this paper we consider Steiner minimum trees (SMT) in the plane, where t he connections can only be along a given set of fixed but arbitrary (not ne cessarily uniform) orientations. The orientations define a metric, called t he general orientation metric. A(sigma), where sigma is the number of orien tations. We prove that in A(sigma) metric, there exists an SMT whose Steine r points belong to an (n - 2)-level grid. This result generalizes a result by Lee and Shen [11], and a result by Du and Hwang [5]. In the former case. the same result was obtained for the special case when all orientations ar e uniform, while in the latter case the same result was proven for the spec ial case when there are only three arbitrary orientations. We then modify t he proof used in the main result for the special case when sigma = 3. i.e,, only three arbitrary orientations are considered, and obtain a better resu lt, which states that there exists an SMT whose Steiner points belong to an inverted right perpendicular n-1/2 inverted left perpendicular -level grid . The result has also been obtained by Lin and Xue [9] using a different ap proach.