Helly-type theorems for approximate covering
Résumé
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.
Domaines
Géométrie algorithmique [cs.CG]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...