Introducing a Theory for the General Solution of Steiner's Problem in Manhattan Space
Y. Wong and M. Pecht
For the engineering and the academic purposes, a set of all global minimum rectilinear Steiner trees (MRSTs) connecting a set of given nodes is defined to be the general solution of Steinerís problem in Manhattan space. A solution defined in the traditional Steinerís problem in Manhattan space has been included in the general solution, contained in a set of graphs called edge-set trees. Each edge-set tree is generated from a rectilinear tree by (a) extending each edge to an edge set containing a set of all shortest rectilinear edges connecting the same pair of points, and (b) extending each Steinerís point to a dynamic Steiner point, that can be moved in specific locations without changing the length of each tree contained in the edge-set tree. In this paper, demonstrated are the relations between the general solution and the edge-set tree, the structures of edge-set trees containing the general solution, and the process for finding the general solution by use of the structures.