Approximating Steiner trees and forests with minimum number of Steiner points

Let R be a finite set of terminals in a convex metric space (M,d). We give approximation algorithms for problems of finding a minimum size set S⊆M of additional points such that the unit-disc graph G[R∪S] of R∪S satisfies some connectivity properties. Let Δ be the maximum number of independent points in a unit ball. For the Steiner Treewith Minimum Number of Steiner Points problem we obtain approximation ratio 1+ln⁡(Δ−1)+ϵ, which in R2 reduces to 1+ln⁡4+ϵ<2.3863+ϵ; this improves the ratios ⌊(Δ+1)/2⌋+1+ϵ of [19] and 2.5+ϵ of [7], respectively. For the Steiner Forestwith Minimum Number of Steiner Points problem we give a simple Δ-approximation algorithm, improving the ratio 2(Δ−1) of [21]. We also simplify the Δ-approximation of [4], when G[R∪S] should be 2-connected.