On the Restricted k-Steiner Tree Problem
share
Given a set P of n points in ℝ^2 and an input line γ in ℝ^2, we present an algorithm that runs in optimal Θ(nlog n) time and Θ(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 ∈γ, 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. ("Generalised k-Steiner Tree Problems in Normed Planes", arXiv:1111.1464) that solves the k-Steiner tree problem in ℝ^2 in O(n^2k) time can be adapted to our setting. For k>1, restricting the (at most) k Steiner points to lie on an input line, the runtime becomes O(n^k). Next we show how the results of Brazil et al. ("Generalised k-Steiner Tree Problems in Normed Planes", arXiv:1111.1464) 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.
READ FULL TEXT