Back to my home page.
Fast Stabbing of Boxes in High Dimensions
Frank Nielsen
![](boxstabbing.jpg)
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:
- Frank Nielsen,
Fast Stabbing of Boxes in High Dimensions,
Theoretical Computer Science (Elsevier Science),
Volume 246, Issue 1-2, 2000.
- Frank Nielsen,
Fast Stabbing of Boxes in High Dimensions,
Europeance Workshop on Computational Geometry,
pp. 101, 1996.
- Frank Nielsen,
Fast Stabbing of Boxes in High Dimensions,
Canadian Conference on Computational Geometry (CCCG),
pp. 87-92, 1996.
- Frank Nielsen,
Fast Stabbing of Boxes in High Dimensions (PDF 364 KB),
INRIA RR-2854,
1996.
Piercing applet
© Copyright notice.
Last updated, 2003.