A polynomial time approximation scheme for rectilinear Steiner minimum tree construction in the presence of obstacles

One problem in VLSI physical designs is to route multiterminal nets in the presence of obstacles. This paper presents a polynomial time approximation scheme for construction of a rectilinear Steiner minimum tree in the presence of obstacles. Given any m rectangular obstacles, n nodes and ε>0, the scheme finds a (1+ε)-approximation to the optimum solution in the time n^o(1ε)/, providing an alternative of previous heuristics. Note that m is assumed to be a constant; otherwise when we solve the sub-problem in a brute force manner, we cannot declare that it can be solved in constant time.