Clustering algorithms based on minimum and maximum spanning trees

ABSTRACT

We consider clustering problems under two different optimization criteria. One is to minimize the maximum intracluster distance (diameter), and the other is to maximize the minimum intercluster distance. In particular, we present an algorithm which partitions a set S of n points in the plane into two subsets so that their larger diameter is minimized in time &Ogr;(n log n) and space &Ogr;(n). Another algorithm with the same bounds computes a k-partition of S for any k so that the minimum intercluster distance is maximized. In both instances it is first shown that an optimal parition is determined by either a maximum or minimum spanning tree of S.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: D. Avis, Diameter Partitioning, Discrete and Computational Geometry, 1, 1986, 265-276.
• 3: P. Brucker, On the Complexity of Clustering Problems, in R.. Henn, B. Korte and W. Oletti, eds., Optimizing and Operations Research, Springer, Berlin, 1977.
• 4: H. Edelsbrunner, H. A. Maurer, F. P. Preparata, A. L. Rosenberg, E. Welzl and D. Wood, Stabbing Line Segments, BIT, 22, 1982, 274-281.
• 5: T. Gonzalez, Algorithms on Sets and Related Problems, Technical Keport, Computer Science Department, University of Oklahoma, 197'5.
• 6: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 7: David S. Johnson, The NP-completeness column: an ongoing guide, Journal of Algorithms, v.9 n.3, p.426-444, September 1988 [doi>10.1016/0196-6774(88)90033-8]
• 8: U. Manber and M. Tompa, Probabilistic, Nondeterministic and Alternating Decision Trees, Tit No. 82-03-01, University of Washington, 1982.
• 9: C. Monma , M. Paterson , S. Suri , F. Yao, Computing Euclidean maximum spanning trees, Proceedings of the fourth annual symposium on Computational geometry, p.241-251, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73418]
• 10: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  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