We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set $S$ of points and a set $\mathcal{ R}$ of geometric objects, and the goal is to find a subset $\mathcal{ R}^*\subseteq\mathcal{ R}$ to cover all points in $S$ such that the \textit{ membership} of $S$ with respect to $\mathcal{ R}^*$, denoted by $\mathsf{ memb}(S,\mathcal{ R}^*)$, is minimized, where $\mathsf{ memb}(S,\mathcal{ R}^*)=\max_{ p\in S}|\{ R\in\mathcal{ R}^*: p\in R\}|$. We achieve the following two main results. * We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time $n^{ O(\mathsf{ opt})}$ where $\mathsf{ opt}$ is the optimum of the problem (i.e., the minimum membership). * We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of $o(\log n)$ in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find $\mathcal{ R}^*\subseteq\mathcal{ R}$ to cover $S$ such that the ply of $\mathcal{ R}^*$ is minimized, where the ply is defined as the maximum number of objects in $\mathcal{ R}^*$ which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in $O(n^{ 12})$ time. We give a significantly simpler constant-approximation algorithm with near-linear running time.
Categories: cs.CG cs.DS