Approximation algorithms for the rectilinear Steiner tree problem with obstacles

The rectilinear Steiner tree problem with a family D of obstacles H[D_i] (1 ≤ i ≤ δ = |D|) is defined as follows: given a rectangular grid graph H = (N, A), a family D of obstacles, and a set P of terminals not contained in any obstacle, find a rectilinear Steiner tree connecting P in H - ∪_DiεD D_i. The case with edge weight being unity is exclusively considered in the paper. First, for the case with D = 0, we propose approximation algorithms by improving those which are already existing. Secondly, we propose other capable approximation algorithms by extending existing ones so that the case with D ≠ 0 may be handled. Evaluation of their performance through experimental results is given.