Fast Approximation Algorithms for Piercing Boxes by Points

Let B = (b1,…, bn be a set of n axis-aligned boxes in ℝd where d ≥ 2 is a constant. The piercing problem is to compute a smallest set of points N ∪ ℝ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(nd/2 polylog(n)). Next, we show that the expected running time can be improved to near-linear using a sampling-based technique, if p = O(n1/(d-1)). 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 ℝ2, we obtain a randomized O(log log p)-approximation algorithm with O(n1/2 polylog(n)) amortized expected update time for insertion or deletion of boxes. For squares in ℝ2, the update time can be improved to O(n1/3 polylog(n)).