Proceedings of the First International Symposium on Microelectronic Package and PCB Technology,
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.




[Home Page] [Articles Page]