A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane

摘要

We present a polynomial time approximation scheme (PTAS) for the Steiner tree problem with polygonal obstacles in the plane with running time O(n log2 n), where n denotes the number of terminals plus obstacle vertices. To this end, we show how a planar spanner of size O(n logn) can be constructed that contains a (1?+?ε)-approximation of the optimal tree. Then one can find an approximately optimal Steiner tree in the spanner using the algorithm of Borradaile et al. (2007) for the Steiner tree problem in planar graphs. We prove this result for the Euclidean metric and also for all uniform orientation metrics, i.e. particularly the rectilinear and octilinear metrics.