Efficient 2-step heuristics for rectilinear Steiner minimal tree construction among obstacles

A primary tree is first constructed without considering obstacles. Intersections of the primary tree edges with obstacles are found out and relevant parts of the primary tree are reconnected to keep clear of obstacles while the total length of the tree being shortest. Moreover, a preprocessing and post-processing are added into the second step to tackle some special treatments and improve the solution quality. The heuristics can deal with multi-obstacle and obstacles of diversified shapes with O(mn) complexity, where m is the number of obstacles and n is the number of terminals. Experimental tests on MCNC benchmarks show that the algorithm can get good results on wire length, its average redundancy compared with minimal trees is 5.31% and the runtime for all cases is within 1 second.