In this paper, we consider the problem of 1-line minimum \(\lambda \) -Steiner tree problem , denoted as the 1L-M \(_{\lambda }\) StT problem. Given a set \(X=\{r_1, r_2, \ldots , \)   \(r_n\}\) of n points in the \(\lambda \) -plane and a straight line l in \(\mathbb R^{2}\) , we need to construct a Steiner tree \(T_{l}\) connecting the n points in X and the straight line l. The objective is to minimize the total cost of such a Steiner tree \(T_{l}\) , i.e., \(\min \{\sum _{e \in T_{l}}\)   \( w(e) \mid T_{l}\) is the mentioned Steiner tree \(\}\) , and if an edge \(e=uv \in T_{l}\) has both endpoints u and v lying on the line l, the weight is defined as \(w(e)=0\) ; Otherwise, it is defined as the distance of the two endpoints u and v in the \(\lambda \) -plane. In particular, if all Steiner points in \(T_{l}\) are constrained to lie on the line l, the problem is denoted as the 1-line minimum \(\lambda \) -spanning tree (1L-M \(_{\lambda }\) ST) problem. We present two main results. (1) By using the strategies of the sweep-line algorithm, we can design an exact algorithm in time \(O(\lambda n\log n)\) to solve the 1L-M \(_{\lambda }\) ST problem; (2) Using some properties of \(\lambda \) -plane, we showed that our algorithm is a \(\rho _{\lambda }\) -approximation algorithm for the 1L-M \(_{\lambda }\) StT problem, where \(\rho _{\lambda }\) is inverse of the Steiner ratio in the \(\lambda \) -plane.

1-Line Minimum \(\lambda \) -Steiner Tree Problem

会议论文
发表日期：

2025年

查看全文

Yinhua Chen,
Jianglin Li,
Wencheng Wang,
Tongquan Zhang

摘要

In this paper, we consider the problem of 1-line minimum \(\lambda \) -Steiner tree problem , denoted as the 1L-M \(_{\lambda }\) StT problem. Given a set \(X=\{r_1, r_2, \ldots , \) \(r_n\}\) of n points in the \(\lambda \) -plane and a straight line l in \(\mathbb R^{2}\) , we need to construct a Steiner tree \(T_{l}\) connecting the n points in X and the straight line l. The objective is to minimize the total cost of such a Steiner tree \(T_{l}\) , i.e., \(\min \{\sum _{e \in T_{l}}\) \( w(e) \mid T_{l}\) is the mentioned Steiner tree \(\}\) , and if an edge \(e=uv \in T_{l}\) has both endpoints u and v lying on the line l, the weight is defined as \(w(e)=0\) ; Otherwise, it is defined as the distance of the two endpoints u and v in the \(\lambda \) -plane. In particular, if all Steiner points in \(T_{l}\) are constrained to lie on the line l, the problem is denoted as the 1-line minimum \(\lambda \) -spanning tree (1L-M \(_{\lambda }\) ST) problem. We present two main results. (1) By using the strategies of the sweep-line algorithm, we can design an exact algorithm in time \(O(\lambda n\log n)\) to solve the 1L-M \(_{\lambda }\) ST problem; (2) Using some properties of \(\lambda \) -plane, we showed that our algorithm is a \(\rho _{\lambda }\) -approximation algorithm for the 1L-M \(_{\lambda }\) StT problem, where \(\rho _{\lambda }\) is inverse of the Steiner ratio in the \(\lambda \) -plane.