RECTILINEAR STEINER TREE CONSTRUCTION BY LOCAL AND GLOBAL REFINEMENT

In this paper, we present a new algorithm for constructing a rectiline ar Steiner tree (RST) for a given set of points. Starting from a recti linear minimum spanning tree (MST), the algorithm works by incremental ly introducing ''good'' Steiner points into the point set and generati ng an MST from the enlarged point set. Steiner points are introduced i n two stages according to their essentiality and cost. In the first st age, they are generated from the local structure of the tree; in the s econd stage, they are generated from the global structure using a loop detection method. The proposed algorithm outperforms most other algor ithms of its class by the fact that the average cost improvement over the rectilinear minimum spanning tree is 10.4%, and its time complexit y is O(n2 log n).