inria-00073837, version 1
Fast Stabbing of Boxes in High Dimensions
N° RR-2854 (1996)
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.}
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- Domaine : Informatique/Autre
- Mots-clés : COMPUTATIONAL GEOMETRY / OUTPUT-SENSITIVE ALGORITHMS
- Référence interne : RR-2854
- inria-00073837, version 1
- http://hal.inria.fr/inria-00073837
- oai:hal.inria.fr:inria-00073837
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mercredi 24 Mai 2006, 13:52:28
- Dernière modification le : Mercredi 31 Mai 2006, 14:24:28






Documents associés

Exporter