s'authentifier
version française rss feed

inria-00073837, version 1

Fast Stabbing of Boxes in High Dimensions

Franck Nielsen 1

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.}

  • Domaine : Informatique/Autre
  • Mots-clés : COMPUTATIONAL GEOMETRY / OUTPUT-SENSITIVE ALGORITHMS
  • Référence interne : RR-2854
 
  • inria-00073837, version 1
  • oai:hal.inria.fr:inria-00073837
  • Contributeur : 
  • Soumis le : Mercredi 24 Mai 2006, 13:52:28
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:28
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...