Hierarchical Steiner Tree Construction in Uniform Orientations

Abstract

In two-dimensional λ-geometry only orientations with angles (iπ/λ), for all i, are allowed, where λ( ≥2) is an integer. Either λ divides 360 or 360 divides λ(λ = 2 corresponds to rectilinear geometry and λ = <inf>∞</inf> corresponds to Euclidean geometry). A hierarchical approach to Steiner tree construction in λ-geometry is proposed. The algorithm runs in time O(n log n) and the length of the constructed tree is at most [o/cos (π/2λ] times (for λ = 2, 3/2 times) the length of an optimal Steiner tree, where n is the cardinality of the point set and it was recently proved that a is [formula Omitted]. How to trade off between the running time of the algorithm and the length of the produced Steiner tree is shown, given “enough” time, an optimal Steiner tree will be obtained. The algorithm is extended to construct a Steiner tree of a set of sub-trees (i.e., partial trees) and runs in O(λN log N) time, where N is the total number of edges of the sub-trees. © 1992 IEEE