Details

Autor(en) / Beteiligte

• Yan, G.Y.
• Albrecht, A.
• Young, G.H.F.
• Wong, C.K.

Titel

The Steiner Tree Problem in Orientation Metrics

Ist Teil von

• Journal of computer and system sciences, 1997-12, Vol.55 (3), p.529-546

Ort / Verlag

Elsevier Inc

Erscheinungsjahr

1997

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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=1Oi, wherek⩽⌈ (n−2)/2⌉.