Let $P=\{C_1,C_2,\ldots ,C_n\}$ be a set of color classes, where each color class $C_i$ consists of a set of points. In this talk, we address a family of covering problems in which each color class must be covered but no two points from the same color class are allowed to be covered by the same geometric object. We consider the case that $P$ is restricted to be on a line and the case that $P$ is anywhere in the Euclidean plane. We examine the following two objectives:
We prove that the problems in this family are NP-complete (or NP-hard) and offer several constant-factor approximation algorithms.
This is joint work with Esther M. Arkin, Aritra Banik, Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell and Marina Simakov.