Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems

In this paper we introduce a new technique for approximation schemes for geometrical optimization problems. As an example problem, we consider the following variant of the geometric Steiner tree problem. Every point u which is not included in the tree costs a penalty of pi(u) units. Furthermore, every Steiner point that we use costs c(S) units. The goal is to minimize the total length of the tree plus the penalties. Our technique yields a polynomial time approximation scheme for the problem, if the points lie in the plane.