Fast Approximation Algorithms for Piercing Boxes by Points

Let B = (b 1, …, b n } 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 ∩ b i ≠ ϕ, 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 p = O ( n 1/( 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 ( n 1/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 ( 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. * A full version of this paper is available on the arXiv [AHRS23].

Authors

• Pankaj K. Agarwal
• Sariel Har-Peled
• Rahul Raychaudhury
• Stavros Sintos

Keywords

No keywords are indexed for this paper.