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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

Contributor : Olivier Devillers <>
Submitted on : Wednesday, July 15, 2009 - 3:58:31 PM
Last modification on : Monday, April 9, 2018 - 12:22:44 PM
Long-term archiving on : Monday, October 15, 2012 - 3:21:07 PM


Files produced by the author(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⟩



Record views


Files downloads