Clustering algorithms based on minimum and maximum spanning trees
Tetsuo Asano, Binay Kumar Bhattacharya, Mark Keil, Fei Yao · 1988
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 Ο(n log n) and space Ο(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.