An Approximation Scheme for Finding Steiner Trees with Obstacles
J. Scott Provan · SIAM Journal on Computing · 1988
We consider the problem of constructing a Steiner minimal tree connecting a given set K of points and lying inside a polygonally bounded, not necessarily simply connected region R in the plane. We first define the path-convex hull of K in R, which is a “sufficiently small” subregion of R guaranteed to contain the Steiner minimal tree. We then give an $\varepsilon $-approximation scheme to find the Steiner minimal tree in R by reducing it to a Steiner tree problem on a “visibility graph” associated with K and the path-convex hull of R. This will be a fully polynomial approximation scheme when K is restricted to lie on a small number of interior points and boundary polygons of R. Several techniques are given which further reduce the region in which the Steiner minimal tree is known to lie, and which extend known results for the Steiner minimal tree problem without obstacles.