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.

Properties and algorithms

It is possible to apply usual algorithms for the minimum spanning tree problem to the complete graph with n2 edges, which yields a complexity of O(n2) with appropriate data structures such as the Fibonacci heap.

Planar case

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 method[1] or a sweepline algorithm.[2]

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.[3]

See also

References

  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.


This article is issued from Wikipedia - version of the Wednesday, March 25, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.