1-line minimum rectilinear steiner trees and related problems

In this paper, motivated by many practical applications, we address the 1-line minimum rectilinear Steiner tree (1L-MRStT) problem, which is a variation of the Euclidean minimum rectilinear Steiner tree problem. More specifically, given n points in the Euclidean plane $${\mathbb {R}}^2$$ R 2 , it is asked to find the location of a line l and a Steiner tree T(l), consisting only of vertical and horizontal line segments plus several successive segments located on this line l, to interconnect these n points and at least one point located on the line l, the objective is to minimize total weight of this Steiner tree T(l), i.e., $$\min \{\sum _{uv\in T(l)} w(u,v)$$ min { ∑ u v ∈ T ( l ) w ( u , v ) | T(l) is a Steiner tree mentioned-above $$\}$$ } , where we define a weight $$w(u,v)=0$$ w ( u , v ) = 0 if the two endpoints u and v of that edge $$uv \in T(l)$$ u v ∈ T ( l ) is located on the line l and otherwise we define a weight w(u, v) as the rectilinear distance between the two endpoints u and v of that edge $$uv \in T(l)$$ u v ∈ T ( l ) . Given a line l as an input in $${\mathbb {R}}^2$$ R 2 , we denote this problem as the 1-line-fixed minimum rectilinear Steiner tree (1LF-MRStT) problem; Furthermore, when the Steiner points of T(l) are all located on the fixed line l, we recall this problem as the 1-line-fixed-constrained minimum rectilinear Steiner tree (1LFC-MRStT) problem. We provide three following main contributions. (1) We design an algorithm $${{\mathcal {A}}}_{C}$$ A C to optimally solve the 1LFC-MRStT problem, where the algorithm $${{\mathcal {A}}}_{C}$$ A C runs in time $$O(n\log n)$$ O ( n log n ) ; (2) We prove that this algorithm $${{\mathcal {A}}}_{C}$$ A C is a 1.5-approximation algorithm to solve the 1LF-MRStT problem; (3) Combining the algorithm $${{\mathcal {A}}}_{C}$$ A C for many times and a key lemma proved by some techniques of computational geometry, we present a 1.5-approximation algorithm to solve the 1L-MRStT problem, where this algorithm runs in time $$O(n^3\log n)$$ O ( n 3 log n ) , and we finally provide another approximation algorithm to solve a special version of the 1L-MRStT problem, where that new algorithm runs in lower time $$O(n^2\log n)$$ O ( n 2 log n ) .