Rectilinear Steiner tree construction by local and global refinement

Ting-Hai Chao, Hsu Yu Chin

2002 · 14 citations · 10 references

Concepts

Abstract

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).< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

References

10