Given a set 3 of : i (i=1, 2, ..., k) orientations (angles) in the plane, one can define a distance function which induces a metric in the plane, called the orientation metric [3]. In the special case where all the angles are equal, we call the metric a uniform orientation metric [2]. Specifically, if there are _ orientations, forming angles i?Γ_, 0 i _&1, with the x-axis, where _ 2 is an integer, we call the metric a * _ -metric. Note that the * 2 -metric is the well-known rectilinear metric and the * corresponds to the Euclidean metric. In this paper, we will concentrate on the * 3 -metric. In the * 2 -metric, Hanan has shown that there exists a solution of the Steiner tree problem such that all Steiner points are on the intersections of grid lines formed by passing lines at directions i?Γ2, i=0, 1, through all demand points. But this is not true in the * 3 -metric. In this paper, we mainly prove the following theorem: Let P, Q, and O i (i=1, 2, ..., k) be the set of n demand points, the set of Steiner points, and the set of the i th generation intersection points, respectively. Then there exists a solution G of the Steiner problem S n such that all Steiner points are in k i=1 O i , where k W (n&2)Γ2X.
] 1997 Academic Press
In fact, let : i and : j be the orientations in 3 that are neighbours of the orientation of the line going through p 1 FIGURE 1.1