Rectilinear Steiner tree construction by local and global refinement

A novel algorithm is presented for constructing a rectilinear Steiner tree (RST) of a given set of points. The algorithm works by incrementally introducing Steiner points from a rectilinear minimum spanning tree (MST) and generating a refined Steiner tree. Steiner points are introduced in two stages according to their importance and cost. In the first stage, they are generated from the local structure of the tree; in the second stage, they are generated from the global structure using a loop detection method. The proposed algorithm outperforms most other algorithms; the average cost improvement over the rectilinear minimum spanning tree is 10.6% and its time complexity is O(n/sup 2/ log n).<>