A computational geometry approach to clustering problems

ABSTRACT

This paper deals with the relationship between cluster analysis and computational geometry describing clustering strategies using a Voronoi diagram approach in general and a line separation approach to improve the efficiency in a special case. We state the following theorems : The set of all centralized 2-clusterings (S1,S2) of a planar point set S with |S1|=a and |S2|=b is exactly the set of all pairs of labels of opposite Voronoi polygons va(S1,S) and vb(S2,S) of Va(S) and Vb(S) respectively. An optimal centralized 2-clustering [centralized divisive hierarchical 2- clustering] can be constructed in &Ogr;(n n1/2 log2n + UF(n) n n1/2 + PF(n)) [&Ogr;(n n1/2 log3n + UF(n) n n1/2 + PF(n)) respectively] steps with PF(n) and UF(n) being the time complexity to compute and update a given clustering measure f.

REFERENCES

• 1: [DE] Day, Edelsbrunner: EFFICIENT ALGORITHMS FOR AGGLOMERATIVE HIERARCHICAL CLUSTERING METHODS, Report F122, Institut fuer Informations- verarbeitung, TU Graz, Graz, Austria.
• 2: [DJ] Dubes, Jain: CLUSTERING METHODOLOGIES IN EXPLORATORY DATA ANALYSIS, in M. C. Yovits (Ed.): Advances in Computers, Vol. 19, 1980.
• 3: Frank K. H. A. Dehne, On O(N^4) Algorithm to Contstruct all Vornoi Diagrams for K Nearest Neighbor Searching, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.160-172, July 18-22, 1983
• 4: [ERS] Edelsbrunner, O'Rouke, Seidel: CONSTRUCTING ARRANGEMENTS OF LINES AND HYPERPLANES WITH APPLICATIONS, Report F123 (see [DE]), 1983.
• 5: [EW1] Edelsbrunner, Welzl: ON THE NUMBER OF LINE- SEPARATIONS OF A FINITE SET IN THE PLANE, Report F97 (see [DE]), 1982.
• 6: [EW2] Edelsbrunner, Welzl: HALFPLANAR RANGE ESTIMATION Report F98 (see [DE]), 1982.
• 7: [EW3] Edelsbrunner, Welzl: HALFPLANAR RANGE SEARCH IN LINEAR SPACE AND O(n^0.695) QUERY TIME, Report F111 (see [DE]), 1983.
• 8: [L] D. T. Lee: AN APPROACH TO FINDING THE K-NEAREST NEIGHBORS IN THE EUCLIDEAN PLANE, Report, Department of Electrical Engineering and Computer Science, Northwestern Univ., Evanston, Il. 60201, USA, 1981.
• 9: [M] Murtagh: EXPECTED-TIME COMPLEXITY RESULTS FOR HIERARCHIC CLUSTERING ALGORITHMS WHICH USE CLUSTER CENTERS, Information Processing Letters 16, 1983.
• 10: [OL] Overmars, Van Leeuwen: MAINTENANCE OF CONFIGURATIONS IN THE PLANE, Journal of Computer and System Science, Vol. 23, No. 2, 1981.
• 11: R. L. Page, ACM Algorithm 479: A minimal spanning tree clustering method, Communications of the ACM, v.17 n.6, p.321-323, June 1974 [doi>10.1145/355616.355617]
• 12: [R] Rohlf: HIERARCHICAL CLUSTERING USING THE MINIMUM SPANNING TREE, The Computer Journal, Vol. 16, No. 1, 1973.
• 13: [S] Schrader: APPROXIMATIONS OF CLUSTERING AND SUBGRAPH PROBLEMS ON TREES, Discrete Applied Math. 6, 1983.
• 14: [SH] Shamos, Hoey: CLOSEST POINT PROBLEMS, Proc. 16th Ann. IEEE Symp. on Found. of Comp. Sci., 1975.
• 15: [W] Willard: POLYGON RETRIEVAL, SIAM J. Comput., Vol. 11, No. 1, 1982.
• 16: F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional 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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

General Terms:
Design, Theory, Verification