Variants of Euclidean k-Center Clusterings

Fix two constant integers k and r. Given a set P of n points on a plane, the Euclidean k-center r-gather clustering problem is the problem to compute a set \(\{ c_1,c_2,\cdots ,c_k \}\) of k points on the plane and a partition \(P_1\cup P_2\cup \cdots \cup P_k\) of P such that each \(P_i\) contains r or more points in P, and the maximum radius of \(P_1, P_2, \cdots , P_k\) is minimized, where the radius of \(P_i\) (with center at \(c_i\) ) is the maximum distance from \(p\in P_i\) to \(c_i\) . If r is 0 then the problem is the ordinary Euclidean k-center clustering problem. This is a geometric version of the k-anonymity which is an important model for privacy preserving. In this paper we design a polynomial-time algorithm to solve the Euclidean k-center r-gather clustering problem when k and r are constant integers. We also design polynomial-time algorithms to solve some related problems.