Steiner Minimal Trees in Rectilinear and Octilinear Planes

This paper considers the Steiner Minimal Tree(SMT)problem in the rectilinear and octi-linear planes.The study is motivated by the physical design of VLSI:The rectilinear case correspondsto the currently used M-architecture,which uses either horizontal or vertical routing,while the octi-linear case corresponds to a new routing technique,X-architecture,that is based on the pervasive useof diagonal directions.The experimental studies show that the X-architecture demonstrates a lengthreduction of more than 10-20%.In this paper,we make a theoretical study on the lengths of SMTsin these two planes.Our mathematical analysis confirms that the length reduction is significant as theprevious experimental studies claimed,but the reduction for three points is not as significant as fortwo points.We also obtain the lower and upper bounds on the expected lengths of SMTs in these twoplanes for arbitrary number of points.