Fast Stabbing of Boxes in High Dimensions

Franck Nielsen 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.}
Type de document :
Rapport
RR-2854, INRIA. 1996
Liste complète des métadonnées

https://hal.inria.fr/inria-00073837
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:52:28
Dernière modification le : samedi 27 janvier 2018 - 01:31:30
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:59:45

Fichiers

Identifiants

  • HAL Id : inria-00073837, version 1

Collections

Citation

Franck Nielsen. Fast Stabbing of Boxes in High Dimensions. RR-2854, INRIA. 1996. 〈inria-00073837〉

Partager

Métriques

Consultations de la notice

145

Téléchargements de fichiers

120