Rectilinear minimum spanning tree
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0c/Rectilinear_minimum_spanning_tree.svg/300px-Rectilinear_minimum_spanning_tree.svg.png)
In graph theory, the rectilinear minimum spanning tree (RMST) of a set of n points in the plane (or more generally, in ) 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.
Properties and algorithms
[edit]By explicitly constructing the complete graph on n vertices, which has n(n-1)/2 edges, a rectilinear minimum spanning tree can be found using existing algorithms for finding a minimum spanning tree. In particular, using Prim's algorithm with an adjacency matrix yields time complexity O(n2).
Planar case
[edit]In the planar case, more efficient algorithms exist. They are based on the idea that connections may only happen with the nearest neighbour of a point in each octant - that is, each of the eight regions of the plane delimited by the coordinate axis from this point and their bisectors.
The resulting graph has only a linear number of edges and can be constructed in O(n log n) using a divide and conquer algorithm[1] or a sweep line algorithm.[2]
Applications
[edit]Electronic design
[edit]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.[3]
See also
[edit]References
[edit]- ^ L.J. Guibas and J. Stolfi, "On computing all northeast nearest neighbors in the L1 metric", Information Processing Letters, 17 (1983), pp. 219--223
- ^ Hai Zhou, Narendra Shenoy, William Nicholls, "Efficient minimum spanning tree construction without Delaunay triangulation", Information Processing Letters 81 (2002) 271–276
- ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal on Applied Mathematics, 30:104–114, 1976.