Finding k points with minimum diameter and related problems

Abstract

We consider the problem of selecting a specified number of points Ic, from a given set S, subject to someoptimization criterion. Problems of this type often arise in statistical clustering and pattern recognition (see Andrews [3] and Hartigan [7]). From an algorithmic standpoint, these problems usually can be solved in time O(&), w h ere n is the number of points in S and c a small constant. Observe that for arbitrary b this time complexity is exponential in the size of the input. Finding general methods to solve this problem for a wide variety of optimization criteria is a challenging and elusive goal and, except for a paper by Dobkin, Drysdale and Guibas [6], the study of this problem has been conducted mainly for fixed values of L. In this paper, we follow the lead of [6] and study the general case of the problem for several natural criteria of optimization. In particular, we give efficient algorithms for the following problems:.