An Efficient Rectilinear and Octilinear Steiner Minimal Tree Algorithm for Multidimensional Environments

Abstract

The rectilinear/octilinear Steiner problem is the problem of connecting a set of terminals Z using orthogonal and diagonal edges with minimum length. This problem has many applications, such as the EDA, VLSI circuit design, fault-tolerant routing in mesh-based broadcast, and Printed Circuit Board (PCB). This paper proposes an obstacle-avoiding 4/8/10/26-directional heuristic algorithm for this problem based on the Areibi's concept, Higher Geometry Maze Routing, and Sollin's minimal spanning tree algorithm. The major contributions of this paper are (1) our work is the first report for the octilinear SMTs in the multidimensional environments, (2) we provide an optimal point-to-point routing without any refinement, and (3) the proposed algorithm has higher adaptability to deal with any irregular environment, and can be extended to the λ-geometry without any extra work, where λ = 2, 4, 8 and ∞ corresponding to rectilinear, 45°, 22.5° and Euclidean geometries respectively.

Keywords

• Higher geometry maze routing
• octilinear
• rectilinear
• Steiner tree