ND8 M INIMUM G EOMETRIC S TEINER T REE

       
• I NSTANCE : Set of points in the plane.
• S OLUTION : A finite set of Steiner points, i.e., .
• M EASURE : 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: Approximable within 1.144 [ 350 ].
• Comment: Approximable within 1.26 in the rectilinear metric [ 48 ] and [ 210 ]. Admits a PTAS if the input is c -local for some constant c>0 , where c -local means that in the minimum spanning tree the longest edge is at least c times as long as the shortest [ 193 ]. 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 [ 300 ].   Variation of the rectilinear metric problem in which there are groups of required vertices and each group must be touched by the Steiner tree is A PX -hard, even if the groups are defined by non-overlapping intervals on one of two parallel lines [ 185 ].
• Garey and Johnson: ND13