Next: MINIMUM GENERALIZED STEINER NETWORK Up: Spanning Trees Previous: MINIMUM STEINER TREE Index

### MINIMUM GEOMETRIC STEINER TREE

- 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 [31].

- Comment: Admits a PTAS for any geometric space of constant dimension d, for example in the rectilinear metric [32]. 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 [388].

- Garey and Johnson: ND13