Rectilinear minimum spanning tree

In graph theory, the rectilinear minimum spanning tree (RMST) of a set of n points in the plane (or more generally in–ℝ^d) is a minimum spanning tree of that set, where the weight of the edge between each pair of points is the rectilinear distance between those two points.

Applications

Electronic design

The problem commonly arises in physical design of electronic circuits. In modern high-density integrated circuits wire routing is performed by wires which consist of segments running horizontally in one layer of metal and vertically in another metal layer. As a result, the wire length between two points is naturally measured with rectilinear distance. Although the routing of a whole net with multiple nodes is better represented by the rectilinear Steiner tree, the RMST provides a reasonable approximation and wire length estimate.