2002 · 14 citations · 10 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputational GeometryOptimizationCombinatorial OptimizationGeometric GraphsGeometric OptimizationGraph AlgorithmsLocal StructureLoop DetectionMinimum Spanning Tree AlgorithmsMinimum Spanning Tree ConstructionMinimum Spanning Tree ProblemSpanning Tree ConstructionSteiner Tree ProblemTree Algorithms
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">></ETX>
10