Helly-type theorems for approximate covering - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Helly-type theorems for approximate covering

Résumé

Let F \cup {U} be a collection of convex sets in R^d such that F covers U. We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume of U; we analyze how small this subset can be depending on the geometry of the elements of F, and show that smooth convex sets and axis parallel squares behave differently. We obtain similar results for surface-to-surface visibility amongst balls in 3 dimensions for a notion of volume related to form factor. For each of these situations, we give an algorithm that takes F and U as input and computes in time O(|F|*|h_e|)$ either a point in U not covered by F or a subset h_e covering U up to a measure e, with |h_e| meeting our combinatorial bounds.
Fichier principal
Vignette du fichier
AppCovering.pdf (237.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00331435 , version 1 (16-10-2008)

Identifiants

  • HAL Id : inria-00331435 , version 1

Citer

Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc. Helly-type theorems for approximate covering. SoCG 2008 - 24th Annual Symposium on Computational Geometry, Jun 2008, College Park, Maryland, United States. pp.120--128. ⟨inria-00331435⟩
266 Consultations
144 Téléchargements

Partager

Gmail Facebook X LinkedIn More