THE STEINER TREE PROBLEM IN ORIENTATION METRICS

Given a set Theta of alpha(i) (i = 1, 2, ..., k) orientations (angles) in the plane, one can define a distance function which induces a metr ic in the plane, called the orientation metric [3]. In the special cas e where all the angles are equal, we call the metric a uniform orienta tion metric [2]. Specifically, if there are a orientations, forming an gles i pi/sigma, 0 less than or equal to i less than or equal to sigma - 1, with the x-axis, where sigma greater than or equal to 2 is an in teger, we call the metric a lambda(sigma)-metric. Note that the lambda (2)-metric is the well-known rectilinear metric and the lambda(infinit y) corresponds to the Euclidean metric. In this paper, we will concent rate on the lambda(3)-metric. In the lambda(2)-metric, Hanan has shown that there exists a solution of the Steiner tree problem such that al l Steiner points are on the intersections of grid lines formed by pass ing lines at directions i pi/2, i = 0, 1, through all demand points. B ut this is not true in the lambda(3)-metric. In this paper, we mainly prove the following theorem: Let P, Q, and O-i (i = 1, 2, ..., k) be t he set of n demand points, the set of Steiner points, and the set of t he ith generation intersection points, respectively. Then there exists a solution G of the Steiner problem S-n such that all Steiner points are in boolean (ORi=1Oi)-O-k, where k less than or equal to inverted r ight perpendicular (n - 2)/2 inverted left perpendicular. (C) 1997 Aca demic Press.