- INSTANCE:
Set
of points in the plane.
- SOLUTION:
A finite set of Steiner points, i.e.,
.
- MEASURE:
The total weight of the minimum spanning tree for the vertex set ,
where the weight of an edge
is the discretized
Euclidean length

*Good News:*Admits a PTAS [33].*Comment:*Admits a PTAS for any geometric space of constant dimension*d*, for example in the rectilinear metric [34]. MINIMUM STEINER TREES WITH OBSTACLES, the problem where a polygonally bounded region*R*is given in the input, and the Steiner tree has to lie inside*R*, admits a FPTAS under some restrictions of the input [409].*Garey and Johnson:*ND13