Geometric red-blue set cover for unit squares and related problems

Research output: Contribution to journalArticlepeer-review

Abstract

We study a geometric version of the RED-BLUE SET COVER problem originally proposed by Carr et al. (2000) [1]: given a red point set, a blue point set, and a set of objects, we want to choose a subset of objects to cover all the blue points, while minimizing the number of red points covered. We prove that the problem is NP-hard even when the objects are unit squares in 2D, and we give the first polynomial-time approximation scheme (PTAS) for this case. The technique we use simplifies and unifies previous PTASs for the weighted geometric set cover problem and the unique maximum coverage problem for 2D unit squares.

Original languageEnglish (US)
Pages (from-to)380-385
Number of pages6
JournalComputational Geometry: Theory and Applications
Volume48
Issue number5
DOIs
StatePublished - 2015

Keywords

  • Approximation algorithms
  • Dynamic programming
  • Geometric set cover

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Geometric red-blue set cover for unit squares and related problems'. Together they form a unique fingerprint.

Cite this