Skip to Main content Skip to Navigation

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.
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download
Contributor : Olivier Devillers <>
Submitted on : Monday, November 5, 2007 - 1:20:25 PM
Last modification on : Friday, September 20, 2019 - 4:56:42 PM
Document(s) archivé(s) le : Friday, November 25, 2016 - 7:13:01 PM


Files produced by the author(s)


  • HAL Id : inria-00179277, version 3



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



Record views


Files downloads