Back to my home page.

Fast Stabbing of Boxes in High Dimensions

Frank Nielsen


Try the Java applet below
Abstract:
We present in this paper a simple yet efficient algorithm for stabbing a set S of n axis-parallel 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)≤c*(S)≤ c(S)≤ b*(S)(1+log2 b*(S))d-1. Since finding 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)≤ 2d-1b*(S) and c(S)=Od(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 finding a minimal-size optimal stabbing point-set of intervals. Finally, we conclude with insights for further research.
 
Key words: computational geometry, output-sensitive algorithms.  
Get the PDF technical report from here.
 
The contents is also described in the Ph. D thesis available online here.
 
Ask me the PS paper (1413 KB size, 23 pages, 5 figures) © Elsevier Science.
 
The original publication is available at Elsevier Science (ScienceDirect).

doi:10.1016/S0304-3975(98)00336-3
Bibtex entry:
@Article{n-fsbhd-2000,
 author = {Frank Nielsen},
 title = {Fast stabbing of boxes in high dimensions},
 journal = {Theoretical Computer Science},
 volume = {246},
 number = {1/2},
 year = {2000},
 issn = {0304-3975},
 pages = {53--75},
 publisher = {Elsevier Science Publishers Ltd.},
 doi= {10.1016/S0304-3975(98)00336-3}
 }

@InProceedings{n-fsbhd-1996,
  author = {Frank Nielsen},
  title = {Fast stabbing of boxes in high dimensions},
  pages = {87--92},
  editor    = {Frank Fiala and
               Evangelos Kranakis and
               J{\"o}rg-R{\"u}diger Sack},
  booktitle     = {Proceedings of the 8th Canadian Conference on Computational Geometry,
               Carleton University, Ottawa, Canada, August 12-15, 1996},
  publisher = {Carleton University Press},
  year      = {1996},
  isbn      = {0-88629-307-3}
}
Related publications:
Piercing applet
© Copyright notice.
Last updated, 2003.