Fast Stabbing of Boxes in High Dimensions
Résumé
We present in this technical report a simple yet efficient algorithm for stabbing a set $§$ of $n$ axis-parallel boxes in $d$-dimensional space with $c$ points in output-sensitive time $O(\time )$ and linear space. Let $c^*$ be the minimum number of points required to stab $§$, then we prove that $c\leq \min{\B\bound}$, where $\rfpxm$ is the rising factorial power: $\rfpxm=\prod _{i=0}^{m-1} (x+i)={{x+m-1}\choosem}$. Since finding a minimal set of $c^*$ points is NP-complete as soon as $d>1$, we obtain a fast precision-sensitive heuristic for stabbing $§$ in output-sensitive time and linear space. In the case of congruent or `constrained' isothetic boxes, our algorithm reports respectively $c\leq 2^{d-1}\cstar$ and $c=O(\cstar)$ stabbing points. Moreover, we show that the bounds we get on $c$ are tight and corroborate our results with some experiments. We also describe an optimal output-sensitiv- e algorithm for finding a minimal-size optimal stabbing point-set of intervals. Finally, we conclude with insights for further research.}