MINIMUM GEOMETRIC STEINER TREE

• INSTANCE: Set $P\subseteq Z\times Z$ of points in the plane.

• SOLUTION: A finite set of Steiner points, i.e., $Q\subseteq Z\times Z$.

• MEASURE: The total weight of the minimum spanning tree for the vertex set $P\cup Q$, where the weight of an edge $\left<(x_1,y_1),(x_2,y_2)\right>$ is the discretized Euclidean length

  
  

  $$\left\lceil\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\right\rceil.$$
  
  

  
  

• 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