A Prim-based Heuristic Algorithm for Obstacle Avoiding Rectilinear Steiner Minimal Tree

Obstacle Avoiding Rectilinear Steiner Minimal Tree (OARSMT) is known to provide the shortest interconnection between n terminals in the presence of m obstacles using the rectilinear distance. We introduce a new line-based graph, which we call the Maneuver Graph that constructs a reduced set of possible paths between any two terminals in the presence of m obstacles with complexity of O(m). Moreover, a dynamic programming algorithm is developed to recover the two-terminal shortest path over the Maneuver Graph with complexity of O(m). Based on the Maneuver Graph we introduce a Prim-based heuristic algorithm that constructs an approximated OARMST in a way analogous to the Obstacle Avoiding Rectilinear Minimum Spanning Tree (OARMST) construction. The nearest terminal is redefined as that one with the shortest interconnection to a terminal, a Steiner or a corner point of the currently constructed sub-tree. This interconnection is established with minimum added tree length and maximum overlap with the already existing interconnections. We show that this algorithm has at worst a complexity of O(n3m2), which is still less than those of 4-steinerization methods. We also show that the algorithm can achieve a percentage-of-improvement about 10% over OARMST which is better than that obtained by the k-steinerization methods.