Fast Approximation Algorithms for Piercing Boxes by Points

Abstract

$\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,\dots ,{\mathsf{b}}_n\}$ be a set of $n$ axis-aligned boxes in ${\Re }^d$ where $d\ge 2$ is a constant. The \emph{piercing problem} is to compute a smallest set of points $\mathbb{N}\subset {\Re }^d$ that hits every box in $\mathcal{B}$, i.e., $\mathbb{N}\cap {\mathsf{b}}_i\ne \varnothing$, for $i=1,\dots ,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 )$.

Appeared in SODA 2024