Rectilinear minimum spanning tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Example of rectilinear minimum spanning tree from random points.

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.

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]

  1. ^ L.J. Guibas and J. Stolfi, "On computing all northeast nearest neighbors in the L1 metric", Information Processing Letters, 17 (1983), pp. 219--223
  2. ^ Hai Zhou, Narendra Shenoy, William Nicholls, "Efficient minimum spanning tree construction without Delaunay triangulation", Information Processing Letters 81 (2002) 271–276
  3. ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal of Applied Mathematics, 30:104–114, 1976.