3530 articles – 5253 Notices  [english version]

inria-00404171, version 1

Helly-type theorems for approximate covering

Julien Demouth () 1, Olivier Devillers () 2, Marc Glisse () 3, Xavier Goaoc () 1

Discrete and Computational Geometry 42, 3 (2009) 379--398

Résumé : Let F ∪ {U } be a collection of convex sets in Rd 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ϵ |) either a point in U not covered by or a subset ϵ covering U up to a measure ϵ, with ϵ meeting our combinatorial bounds.

  • 1 :  VEGAS (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2 :  GEOMETRICA (INRIA Sophia Antipolis / INRIA Saclay - Ile de France)
  • INRIA
  • 3 :  Grenoble Images Parole Signal Automatique (GIPSA-lab)
  • CNRS : UMR5216 – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – Université Stendhal - Grenoble III – Institut Polytechnique de Grenoble - Grenoble Institute of Technology
  • Domaine : Informatique/Géométrie algorithmique
 
  • inria-00404171, version 1
  • http://hal.inria.fr/inria-00404171
  • oai:hal.inria.fr:inria-00404171
  • Contributeur : Olivier Devillers <>
  • Soumis le : Mercredi 15 Juillet 2009, 15:58:31
  • Dernière modification le : Jeudi 12 Novembre 2009, 11:42:35