Conflict-Free Covering

Gui Citovsky, Stony Brook University

November 24, 2015

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:

  1. Cover at least one point from each color class.
  2. Cover exactly one point from each color class.

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.