Beijing China, pp. 114-115, September 19-23, 1994.

**Introducing a Theory for the General Solution of Steiner's
Problem in Manhattan Space**

Y. Wong and M. Pecht

**Abstract:**

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.