Complexity and Approximation of the Rectilinear Steiner Tree Problem

Given a finite set K of terminals in the plane. A rectilinear Steiner minimum tree for K (RST) is a tree which interconnects among these terminals using only horizontal and vertical lines of shortest possible length containing Steiner point. We show the complexity of RST i.e. belongs to NP-complete. Moreover we present an approximative method of determining the solution of RST problem proposed by Sanjeev Arora in 1996, Arora's Approximation Scheme. This algorithm has time complexity polynomial in the number of terminals for a fixed performance ratio 1 + Epsilon