The Steiner Tree Problem in Orientation Metrics

摘要

Given a setΘ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 anglesiπ/σ, 0⩽i⩽σ−1, with thex-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 directionsiπ/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: LetP,Q, andOi(i=1, 2, …, k) be the set ofndemand points, the set of Steiner points, and the set of theith generation intersection points, respectively. Then there exists a solutionGof the Steiner problemSnsuch that all Steiner points are in ∪ki=1 Oi, wherek⩽⌈ (n−2)/2⌉.