Helly-type theorems for approximate covering

Julien Demouth 1 Olivier Devillers 2 Marc Glisse 1 Xavier Goaoc 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 GEOMETRICA - Geometric computing
INRIA Futurs, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size O(epsilon^((1-d)/2)polylog 1/epsilon). We give an example showing that this bound is tight in the worst-case, up to a logarithmic factor, and deduce an algorithm to compute such a small subset of F. We then extend these results in several directions, including covering boxes by boxes and visibility among disjoint unit balls in R3.
Type de document :
Rapport
[Research Report] RR-6342, INRIA. 2007, pp.12
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00179277
Contributeur : Olivier Devillers <>
Soumis le : lundi 5 novembre 2007 - 13:20:25
Dernière modification le : jeudi 11 janvier 2018 - 16:42:48
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 19:13:01

Fichier

RR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00179277, version 3

Citation

Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc. Helly-type theorems for approximate covering. [Research Report] RR-6342, INRIA. 2007, pp.12. 〈inria-00179277v3〉

Partager

Métriques

Consultations de la notice

413

Téléchargements de fichiers

119