Steiner Tree Demonstration Applet
This applet illustrates how a Steiner Rectilinear Tree (SRT) can be constructed by adding Steiner Points to an existing set of terminals. The user can edit the number and location of a set of terminals and then add and/or delete Steiner points to evaluate their effect on the length of the resulting tree. The applet then displays the Rectilinear Minimum Spanning that includes both the termianls and Steiner points to form a Steiner Rectilinear Tree. A Minimal Steiner Rectilinear Tree (MSRT) is a minimum-length Steiner Tree. This applet does not compute the minimal Steiner Tree but instead lets the user experiment with different choices of Steiner points to discover their impact on overall length. To Use the Applet Terminals are displayed as small squares; Steiner points are displayed as circles. Edges show the edges of a Rectilinear Minimum Spanning Tree that connects terminals and Steiner Points. The applet operates in two modes: Terminal Edit mode, and Steiner Point Edit mode. The use can switch between the two modes by clicking the "STMODE" button. Terminal Edit mode is used to add, delete, or move terminal nodes as follows:
In Steiner Point Edit mode, Steiner points may be added and removed at locations on the "Hanan Grid", which is shown in gray (see explanation below) as follows:
About Steiner Trees Given a set of terminal points in a plane, a Minimum Steiner
Rectilinear Tree (SRT) is a set of edges which connects all the
terminals along with a set of added "Steiner points" such that the
rectilinear distance is minimized. F. Hwang [Hwang, 1976]
proved that the length of a Steiner tree can be up to 3/2 times shorter
than a Rectilinear Minimum Spanning Tree on the same set of terminals. M. Hanan [Hanan, 1966] proved that a Minimum RST can be
constructed using points on a grid defined by the x and y coordinates
of the terminal points (now known as the Hanan Grid). The Minimum Steiner Rectilinear tree problem is be NP-Hard [Garey, 1977], which inidicates that any exact
algorithm will have a worst-case execution time that grows
exponentially with the problem size. In spite of this, exact
algorithms such as have been found that complete in reasonable
time for large examples [Warme 2003]. Several heuristics have also been developed; we plan to add a
brief survey along with animations of some key heuristics in the future. J. Ganley. "The Steiner Tree Page", http://ganley.org/steiner.
M. Garey and D.
Johnson, "The rectilinear Steiner tree problem is NP-complete",
SIAM Journal on Applied
Mathematics, Vol. 32 pp. 826-834, 1977. M. Hanan, "On Steiner's Problem with Rectilinear Distance", SIAM Journal of Applied Math, Vol.
14, No. 2, March 1966, pp. 255-265. F. Hwang, "On Steiner Minimal Trees with Rectilinear
Distance", SIAM Journal of Applied
Mathematics, Vol. 30, No. 1, January 1976, pp. 104-114. F. Hwang, D. Richards, and P. Winter, The Steiner Tree Problem,
North-Holland, 1992. D. Warme, P. Winter, and M. Zachariasen, "GeoSteiner 3.1 Home
Page", January 2003 http://www.diku.dk/geosteiner. Acknowledgement
|