The Class Cover Problem with Boxes

by S. Bereg, S. Cabello, J. M. Díaz-Báñez, P. Pérez-Lantero, C. Seara, and I. V. Molina.

Abstract: Given r red and b blue points, find smallest number of boxes covering blue points and avoiding red points. For example, 4 boxes cover blue points in Figure below.

We prove the NP-hardness of the stated problem, and give either exact or approximate algorithms depending on the type of rectangles considered. If the covering boxes are vertical or horizontal strips we give an efficient algorithm that runs in O(r log r + b log b + b\sqrt{r}) time. For covering with oriented half-strips an optimal O((r + b) log(min{r, b}))-time algorithm is shown. We prove that the problem remains NP-hard if the covering boxes are half-strips oriented in any of the four orientations, and show that there exists an O(1)-approximation algorithm. We also give an NP-hardness proof if the covering boxes are squares. In this situation, we show that there exists an O(1)-approximation algorithm.

pdf file submitted to a journal.



@inproceedings{bcdpsm-cc-10
, author = {Sergey Bereg and Sergio Cabello and Jos{\'e} Miguel
D\'{\i}az-B{\'a}{\~n}ez and Pablo P{\'e}rez-Lantero and Carlos Seara and
Inmaculada Ventura Molina}
, title = {The Class Cover Problem with Boxes}
, booktitle = {Proc. 26th European Workshop Comput. Geom.}
, year = {2010}
, pages = {69--72}
, url = {http://2010.eurocg.org}
}