Helly-type theorems for approximate covering

Julien Demouth 1 Olivier Devillers 2 Marc Glisse 3 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
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
GIPSA-DIS - Département Images et Signal
Abstract : Let F ∪ {U } be a collection of convex sets in Rd such that F covers U . We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume of U ; we analyze how small this subset can be depending on the geometry of the elements of F , and show that smooth convex sets and axis parallel squares behave differently. We obtain similar results for surface-to-surface visibility amongst balls in 3 dimensions for a notion of volume related to form factor. For each of these situations, we give an algorithm that takes F and U as input and computes in time O (|F | ∗ |Hϵ |) either a point in U not covered by or a subset ϵ covering U up to a measure ϵ, with ϵ meeting our combinatorial bounds.
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 2009, 42 (3), pp.379--398. 〈10.1007/s00454-009-9167-1〉
Liste complète des métadonnées

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

Contributeur : Olivier Devillers <>
Soumis le : mercredi 15 juillet 2009 - 15:58:31
Dernière modification le : lundi 9 avril 2018 - 12:22:44
Document(s) archivé(s) le : lundi 15 octobre 2012 - 15:21:07


Fichiers produits par l'(les) auteur(s)



Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc. Helly-type theorems for approximate covering. Discrete and Computational Geometry, Springer Verlag, 2009, 42 (3), pp.379--398. 〈10.1007/s00454-009-9167-1〉. 〈inria-00404171〉



Consultations de la notice


Téléchargements de fichiers