Fast Approximation Algorithms for Piercing Boxes by Points

Let B = {b1, ..., bn} be a set of n axis-aligned boxes in R^d where d ≥ 2 is a constant. The piercing problem is to compute a smallest set of points N ⊂ R^d that hits every box in B, i.e., N ∩bi ≠ ∅, for i = 1, ..., n. The problem is known to be NP-Hard. Let p:= p(B), the piercing number be the minimum size of a piercing set of B. We first present a randomized O(log log p)approximation algorithm with expected running time O(n^d/2 polylog(n)). Next, we show that the expected running time can be improved to near-linear using a sampling-based technique, if (Equation presented). Specifically, in the plane, the improved running time is O(n log p), assuming p < n/log^Ω(1) n. Finally, we study the dynamic version of the piercing problem where boxes can be inserted or deleted. For boxes in R², we obtain a randomized O(log log p)-approximation algorithm with O(n^1/2 polylog(n)) amortized expected update time for insertion or deletion of boxes. For squares in R², the update time can be improved to O(n^1/3 polylog(n)). Our algorithms are based on the multiplicative weight-update (MWU) method and require the construction of a weak ε-net for a point set with respect to boxes. A key idea of our work is to exploit the duality between the piercing set and independent set (for boxes) to speed up our MWU. We also present a simpler and slightly more efficient algorithm for constructing a weak ε-net than in [Ezr10], which is of independent interest. Our approach also yields a simpler algorithm for constructing (regular) ε-nets with respect to boxes for d = 2, 3.

Duke Scholars

Author Pankaj K. Agarwal Computer Science