STEINER TREE FOR ROUTING
4.2
The Rectilinear Steiner tree problem can be
stated as, given n points in the plane, it is required to interconnect
them all by a shortest network which consists only of vertical and horizontal
line segments. It can be shown that such a network is a tree whose vertices are
the input points and Steiner points. Set of finite points called Hannon Points
has to be identified. In Steiner tree problem the Euclidean distance is
replaced with the rectilinear distance.
The spanning tree is constructed by connecting the Steiner point with
closest points in the four regions(North, East, south, West).If the connection
forms a cycle, then cycle should be identified and largest segment should be
removed. By introducing Steiner points
we can get the minimum length Steiner tree