Given a set of points $P$ and axis-aligned rectangles $mathcal{R}$ in the plane, a point $p in P$ is called emph{exposed} if it lies outside all rectangles in $mathcal{R}$. In the emph{max-exposure problem}, given an integer parameter $k$, we want to delete $k$ rectangles from $mathcal{R}$ so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in $mathcal{R}$ are translates of two fixed rectangles. However, if $mathcal{R}$ only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For range space defined by general rectangles, we present a simple $O(k)$ bicriteria approximation algorithm; that is by deleting $O(k^2)$ rectangles, we can expose at least $Omega(1/k)$ of the optimal number of points.
Download