Computing Euclidean maximum spanning trees

ABSTRACT

An algorithm is presented for finding a maximum-weight spanning tree of a set of n points in the Euclidean plane, where the weight of an edge (pi, pj) equals the Euclidean distance between the points pi and pj. The algorithm runs in time &Ogr; (n logn) and requires &Ogr; (n) space. If the points are vertices of a convex polygon (given in order along the boundary), then our algorithm requires only a linear amount of time and space. These bounds are the best possible in the algebraic computation-tree model. We also establish various properties of maximum spanning trees that can be exploited to solve other geometric problems.

REFERENCES

• 1: T. Asano , B. Bhattacharya , M. Keil , F. Yao, Clustering algorithms based on minimum and maximum spanning trees, Proceedings of the fourth annual symposium on Computational geometry, p.252-257, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73419]
• 2: A. Aggarwal, M. Klawe, S. Moran, P. Shor and R. Wilber, Geometric applications of a matrix searching algorithm, Algorithmica 2, 1987, pp. 195-208.
• 3: D. Avis, Diameter Partitioning, Discrete and Computational Geometry, 1, 1986, pp. 265-276.
• 4: Bernard Chazelle, How to search history, Information and Control, v.64 n.1-3, p.77-99, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80045-0]
• 5: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 6: Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
• 7: R. Graham and P. Hell, On the history of minimum spanning tree problem, Annals of History of Computing, 7, 1985.
• 8: S.C. Johnson, Hierarchical clustering schemes, Psychometrika, 32, 1967, pp. 241-254.
• 9: D.S. Johnson, NP-completeness column, J. of Algorithms 3, 1982.
• 10: D.T. Lee, Farthest point Voronoi diagrams and applications, TR 80-11-FC-04, Northwestern University, 1980.
• 11: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 12: M.L Shamos, Computational Geometry, University Microfilms, Ann Arbor, MI, 1978.
• 13: R.R. Sokal and P.H. Sneath, Principles of Numerical Taxonomy, W.H. Freeman, San Francisco, 1963.
• 14: G.T. Toussaint and B.K. Bhattacharya, On geometric algorithms that use the furthestpoint Voronoi diagrams, TR SOCS-81.3, McGill University, 1981.
• 15: A.C. Yao, On constructing minimum spanning trees in k-dimensional spaces and related problems, SIAM J. of Computing 11, 1982, pp. 721-736.
• 16: R.A. Jarvis, Shared near neighbor maximal spanning trees for cluster analysis, Proc. of Fourth Joint Conference on Pattern Recognition, Kyoto, Japan, 1978.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Region growing, partitioning
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Design, Measurement, Performance, Theory