The Maximum Exposure Problem
share
Given a set of points P and axis-aligned rectangles ℛ in the plane, a point p ∈ P is called exposed if it lies outside all rectangles in ℛ. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from ℛ 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 ℛ are translates of two fixed rectangles. However, if ℛ 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 Ω(1/k) of the optimal number of points.
READ FULL TEXT