3526 articles – 5249 Notices  [english version]

inria-00331435, version 1

Helly-type theorems for approximate covering

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

Proceedings of the twenty-fourth annual symposium on Computational geometry - SCG '08 (2008) 120--128

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.

  • 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
  • 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-00331435, version 1
  • http://hal.inria.fr/inria-00331435
  • oai:hal.inria.fr:inria-00331435
  • Contributeur : Xavier Goaoc <>
  • Soumis le : Jeudi 16 Octobre 2008, 16:21:03
  • Dernière modification le : Lundi 20 Octobre 2008, 09:36:24