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.
Example of rectilinear minimum spanning tree from random points.
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 caseedit
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 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]
^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
rectilinear, minimum, spanning, tree, graph, theory, rectilinear, minimum, spanning, tree, rmst, points, plane, more, generally, ℝd, minimum, spanning, tree, that, where, weight, edge, between, each, pair, points, rectilinear, distance, between, those, 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 Example of rectilinear minimum spanning tree from random points Contents 1 Properties and algorithms 1 1 Planar case 2 Applications 2 1 Electronic design 3 See also 4 ReferencesProperties and algorithms editBy 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 editElectronic 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 editEuclidean minimum spanning treeReferences 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 Retrieved from https en wikipedia org w index php title Rectilinear minimum spanning tree amp oldid 922793779, wikipedia, wiki, book, books, library,
