Fast stabbing of boxes in high dimensions

✍ Scribed by Frank Nielsen

• Book ID: 104326642
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 382 KB
• Volume: 246
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00336-3

✦ Synopsis

We present in this paper a simple yet e cient algorithm for stabbing a set S of n axisparallel boxes in d-dimensional space with c(S) points in output-sensitive time O(dn log c(S)) and linear space. Let c * (S) and b * (S) be, respectively, the minimum number of points required to stab S and the maximum number of pairwise disjoint boxes of S. We prove that b * (S)6c * (S)6c(S)6b * (S)(1+log 2 b * (S)) d-1 . Since ÿnding a minimal set of c * (S) points is NP-complete as soon as d¿1, we obtain a fast precision-sensitive heuristic for stabbing S whose quality does not depend on the input size. In the case of congruent or constrained isothetic boxes, our algorithm reports, respectively, c(S)62 d-1 b * (S) and c(S) = O d (b * (S)) stabbing points. Moreover, we show that the bounds we get on c(S) are asymptotically tight and corroborate our results with some experiments. We also describe an optimal output-sensitive algorithm for ÿnding a minimal-size optimal stabbing point-set of intervals. Finally, we conclude with insights for further research.