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)
1
2

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.

Keywords

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

Dates and versions

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

Identifiers

  • HAL Id : inria-00179277 , version 3

Cite

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

Share

Gmail Facebook Twitter LinkedIn More