Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem

In this paper, we consider the 1-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem and defined as follows. Given a set $$P=\{r_1,r_2,\ldots , r_n\}$$P={r1,r2,…,rn} of n points in the Euclidean plane $$\mathbb {R}^2$$R2, we are asked to find the location of a line l and an Euclidean Steiner tree T(l) in $$\mathbb {R}^2$$R2 such that at least one Steiner point is located at such a line l, the objective is to minimize total weight of such an Euclidean Steiner tree T(l), i.e., $$\min \{\sum _{e\in T(l)} w(e)~|~T(l)$$min{∑e∈T(l)w(e)|T(l) is an Euclidean Steiner tree as mentioned-above$$\}$$}, where we define weight $$w(e)=0$$w(e)=0 if the end-points u, v of each edge $$e=uv \in T(l)$$e=uv∈T(l) are both located at such a line l and otherwise we denote weight w(e) to be the Euclidean distance between u and v. Given a fixed line l as an input in $$\mathbb {R}^2$$R2, we refer this problem as the 1-line-fixed Euclidean minimum Steiner tree problem; In addition, when Steiner points added are all located at such a fixed line l, we refer this problem as the constrained Euclidean minimum Steiner tree problem. We obtain the following two main results. (1) Using a polynomial-time exact algorithm to find a constrained Euclidean minimum Steiner tree, we can design a 1.214-approximation algorithm to solve the 1-line-fixed Euclidean minimum Steiner tree problem, and this algorithm runs in time $$O(n\log n)$$O(nlogn); (2) Using a combination of the algorithm designed in (1) for many times, a technique of finding linear facility location and an important lemma proved by some techniques of computational geometry, we can provide a 1.214-approximation algorithm to solve the 1-line Euclidean minimum Steiner tree problem, and this new algorithm runs in time $$O(n^3\log n)$$O(n3logn).