Separating Colored Points with Minimum Number of Rectangles

Abstract

In this paper we study the following problem: Given $k$ disjoint sets of points, $P_1,\dots ,P_k$ on the plane, find a minimum cardinality set $\mathcal{T}$ of arbitrary rectangles such that each rectangle contains points of just one set $P_i$ but not the others. We prove the NP-hardness of this problem.