Efficient minimum spanning tree construction without Delaunay triangulation

ABSTRACT

Minimum spanning tree problem is a very important problem in VLSI CAD. Given n points in a plane, a minimum spanning tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least ω(n2) time. More efficient approaches find a minimum spanning tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning tree construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(n log n) sweep-line algorithm to construct a rectilinear minimum spanning tree without using Delaunay triangulation.

REFERENCES

• 1: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 2: Steven Fortune. A sweepline algorithm for voronoi diagrams. Algorithmica, 2:153-174, 1987.
• 3: Linda L. Deneen Gary M. Shute and Clark D. Thomborson. An O(n log n) Plane-Sweep Algorithm for L1 and L1 Delaunay Triangulation. In Algorithmica, volume 6, pages 207-221, 1991.
• 4: Leo J. Guibas and Jorge Stolfi. On computing all north-east nearest neighbors in the L1 metric. Information Processing Letters, 17(4):219-223, 8 November 1983.
• 5: F. K. Hwang, An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees, Journal of the ACM (JACM), v.26 n.2, p.177-182, April 1979 [doi>10.1145/322123.322124]
• 6: E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.
• 7: Edward M. McCreight. Priority search trees. SIAM Journal of Computing, 14(2):257-276, May 1985.
• 8: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 9: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 10: Gabriel Robins and Jeffrey S. Salowe. Low-degree minimum spanning tree. Discrete and Computational Geometry, 14:151-165, September 1995.
• 11: Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721- 736, November 1982.
• 12: S. Q. Zheng, J. S. Lim, and S. S. Iyengar. Finding obstacle-avoiding shortest paths using implicit connection graphs. IEEE Transactions on Computer Aided Design, 15(1):103-110, January 1996.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Performance, Theory