On the restricted k-Steiner tree problem

Given a set P of n points in $$\mathbb {R}^2$$ R 2 and an input line $$\gamma $$ γ in $$\mathbb {R}^2$$ R 2 , we present an algorithm that runs in optimal $$\varTheta (n\log n)$$ Θ ( n log n ) time and $$\varTheta (n)$$ Θ ( n ) space to solve a restricted version of the 1-Steiner tree problem. Our algorithm returns a minimum-weight tree interconnecting P using at most one Steiner point $$s \in \gamma $$ s ∈ γ , where edges are weighted by the Euclidean distance between their endpoints. We then extend the result to j input lines. Following this, we show how the algorithm of Brazil et al. in Algorithmica 71(1):66–86 that solves the k-Steiner tree problem in $$\mathbb {R}^2$$ R 2 in $$O(n^{2k})$$ O ( n 2 k ) time can be adapted to our setting. For $$k>1$$ k > 1 , restricting the (at most) k Steiner points to lie on an input line, the runtime becomes $$O(n^{k})$$ O ( n k ) . Next we show how the results of Brazil et al. in Algorithmica 71(1):66–86 allow us to maintain the same time and space bounds while extending to some non-Euclidean norms and different tree cost functions. Lastly, we extend the result to j input curves.