Skip to Main content Skip to Navigation
Reports

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

https://hal.inria.fr/inria-00179277
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

File

RR.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00179277, version 3

Collections

Citation

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

Share

Metrics

Record views

478

Files downloads

269