Static and Dynamic Algorithms for k-Point Clustering Problems

Let S be a set of n points in d-space, where d ≥ 2 is a constant, and let 1 ≤ k ≤ n be an integer. A unified approach is given for solving the problem of finding a subset of S of size k that minimizes some closeness measure, such as the diameter, perimeter or the circumradius. Moreover, data structures are given that maintain such a subset under insertions and deletions of points.