Fast Approximation Algorithms for Piercing Boxes by Points

newcommandpoptp newcommandReℝnewcommandNN newcommandBXB newcommandbbmathsfb newcommandepsvarepsilon newcommandpolylogpolylog Let B=mathsfb1, ldots ,mathsfbn be a set of n axis-aligned boxes in Red where d≥2 is a constant. The piercing problem is to compute a smallest set of points N subset Red that hits every box in B, i.e., Ncap mathsfbineq emptyset, for i=1,ldots, n. Let popt=popt(B), the piercing number be the minimum size of a piercing set of B. We present a randomized O(d2loglog popt)-approximation algorithm with expected running time O(nd/2polylog n). Next, we present a faster O(nlog d+1)-time algorithm but with a slightly inferior approximation factor of O(24dloglogpopt). The running time of both algorithms can be improved to near-linear using a sampling-based technique, if popt = O(n1/d). For the dynamic version of the problem in the plane, we obtain a randomized O(loglogpopt)-approximation algorithm with O(n1/2polylog n ) amortized expected update time for insertion or deletion of boxes. For squares in Re2, the update time can be improved to O(n1/3polylog n ).