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

Contributeur : Olivier Devillers <>
Soumis le : mercredi 15 juillet 2009 - 15:58:31
Dernière modification le : jeudi 9 février 2017 - 15:48:27
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 du document