$\newcommand{ \popt}{ { \mathcal{ p}}} \newcommand{ \Re}{ \mathbb{ R}}\newcommand{ \N}{ { \mathcal{ N}}} \newcommand{ \BX}{ \mathcal{ B}} \newcommand{ \bb}{ \mathsf{ b}} \newcommand{ \eps}{ \varepsilon} \newcommand{ \polylog}{ \mathrm{ polylog}} $ Let $\mathcal{ B}=\{ \mathsf{ b}_1, \ldots ,\mathsf{ b}_n\}$ be a set of $n$ axis-aligned boxes in $\Re^d$ where $d\geq2$ is a constant. The \emph{ piercing problem} is to compute a smallest set of points $\N \subset \Re^d$ that hits every box in $\mathcal{ B}$, i.e., $\N\cap \mathsf{ b}_i\neq \emptyset$, for $i=1,\ldots, n$. Let $\popt=\popt(\mathcal{ B})$, the \emph{ piercing number} be the minimum size of a piercing set of $\mathcal{ B}$. We present a randomized $O(d^2\log\log \popt)$-approximation algorithm with expected running time $O(n^{ d/2}\polylog n)$. Next, we present a faster $O(n^{ \log d+1})$-time algorithm but with a slightly inferior approximation factor of $O(2^{ 4d}\log\log\popt)$. The running time of both algorithms can be improved to near-linear using a sampling-based technique, if $\popt = O(n^{ 1/d})$. For the dynamic version of the problem in the plane, we obtain a randomized $O(\log\log\popt)$-approximation algorithm with $O(n^{ 1/2}\polylog n )$ amortized expected update time for insertion or deletion of boxes. For squares in $\Re^2$, the update time can be improved to $O(n^{ 1/3}\polylog n )$.
Categories: cs.CG