Obstacle-avoiding rectilinear Steiner minimum tree construction: An optimal approach

In this paper, we present an efficient method to solve the obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem optimally. Our work is a major improvement over the work proposed in. First, a new kind of full Steiner trees (FSTs) called obstacle-avoiding full Steiner trees (OAFSTs) is proposed. We show that for any OARSMT problem there exists an optimal tree composed of OAFSTs only. We then extend the proofs on the possible topologies of FSTs in to find the possible topologies of OAFSTs, showing that OAFSTs can be constructed easily. A two-phase algorithm for the construction of OARSMTs is then developed. In the first phase, a sufficient number of OAFSTs are generated. In the second phase, the OAFSTs are used to construct an OARSMT. Experimental results on several benchmarks show that the proposed method achieves 185 times speedup on average and is able to solve more benchmarks than the approach in.