Helly-type theorems for approximate covering

Julien Demouth 1 Olivier Devillers 2 Marc Glisse 3 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
CRISAM - Inria Sophia Antipolis - Méditerranée
3 GIPSA-GPIG - GPIG
GIPSA-DIS - Département Images et Signal
Abstract : 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.
Type de document :
Communication dans un congrès
Proceedings of the twenty-fourth annual symposium on Computational geometry - SCG '08, Jun 2008, Washington, United States. ACM, pp.120--128, 2008
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00331435
Contributeur : Xavier Goaoc <>
Soumis le : jeudi 16 octobre 2008 - 16:21:03
Dernière modification le : jeudi 11 janvier 2018 - 16:22:45
Document(s) archivé(s) le : mardi 9 octobre 2012 - 13:51:09

Fichier

AppCovering.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00331435, version 1

Citation

Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc. Helly-type theorems for approximate covering. Proceedings of the twenty-fourth annual symposium on Computational geometry - SCG '08, Jun 2008, Washington, United States. ACM, pp.120--128, 2008. 〈inria-00331435〉

Partager

Métriques

Consultations de la notice

374

Téléchargements de fichiers

119