
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Effective Use of Geometric Information for Clustering and Related Topics
Tetsuo ASANO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E83D
No.3
pp.418427 Publication Date: 2000/03/25 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: INVITED SURVEY PAPER Category: Algorithms for Geometric Problems Keyword: bipartite graph, coloring, computational geometry, diameter, duality transform, geometric clustering, intercluster distance, maximum spanning tree, separability, Voronoi diagram,
Full Text: PDF(436.9KB)>>
Summary:
This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NPcomplete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

