Red–Blue <i>k</i>-Center Clustering with Distance Constraints

Abstract

We consider a variant of the k-center clustering problem in IRd, where the centers can be divided into two subsets—one, the red centers of size p, and the other, the blue centers of size q, such that p+q=k, and each red center and each blue center must be a distance of at least some given α≥0 apart. The aim is to minimize the covering radius. We provide a bi-criteria approximation algorithm for the problem and a polynomial time algorithm for the constrained problem where all centers must lie on a given line ℓ. Additionally, we present a polynomial time algorithm for the case where only the orientation of the line is fixed in the plane (d=2), although the algorithm works even in IRd by constraining the line to lie in a plane and with a fixed orientation.

Keywords

• algorithms
• facility location
• computational geometry
• clustering