Helly-type theorems for approximate covering - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2007

Helly-type theorems for approximate covering

(1) , (2) , (1) , (1)


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.


Fichier principal
Vignette du fichier
RR.pdf (428.5 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00179277 , version 1 (15-10-2007)
inria-00179277 , version 2 (05-11-2007)
inria-00179277 , version 3 (05-11-2007)


  • 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⟩
224 View
161 Download


Gmail Facebook Twitter LinkedIn More