| RMST Applet
Prim's Algorithm for Rectilinear Minimum Spanning
This applet illustrates the construction of a Rectilinear
Spanning Tree (RSMT) using Prim's Algorithm. A RMST connects
all terminals together in a way that minimizes the overall distance of
connections in this tree. Prim's Algorithm operates incrementally on
a partial tree starting with a single terminal - on each iteration, it
adds an edge between the partial tree and the terminal that is closest
to any terminal in the partial tree.
To Use the Applet
This applet creates a small number of terminals at random locations.
Use the "VCR" controls to start, pause, single-step or stop the
There are several ways to edit the terminals shown in the
Note that editing terminals will stop a running
animation since the previously executed steps may no longer be valid.
- Add a terminal by clicking at a location where no terminal
- Move a terminal by clicking and dragging to
the desired location.
- Delete a terminal by pressing the CONTROL key and clicking
Clicking the "AUTO" button places the applet in automatic mode, where
the complete RMST is recalculated whenever the terminals are edited or
Mininimum Spanning Trees
Given a set of terminal points in a plane, a rectilinear
minimum spanning tree is a set of edges which connects all the
terminals with minimum rectilinear distance. Rectilinear distance
(also called "Manhattan Distance") is the sum of the horizontal and
vertical distance between two points. It is used instead of
Euclidean distance in VLSI CAD
applications because VLSI processes support only horizontal and
The RMST can be used as an estimate of the length of
a net that connects together multiple terminals.
The RMST Problem is a special case of the Minimum Spanning Tree
problem studied in Computer Science Algorithms textbooks in that the
distances between the points imply a complete graph.
A. Kahng and I. Mandoiu, "GSRC Bookshelf RMST-Pack: Rectilinear Minimum
Algorithms", June 2001. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/RMST/.
M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Design,
This RMST code in this applet is derived from Joseph Ganley's
"Interconnection Tree Applet",
which can be found at http://ganley.org/software/tree.html