Greedy Geometric Optimization Algorithms for Collection of Balls

Résumé : Les boules jouent un rôle central en modélisation géométrique pour deux raisons: d'une part la transformée associée à l'axe médian permet de représenter un objet solide comme une union in nie de boules; d'autre part, certaines formes, et les modèles moléculaires de van der Waals en particulier, sont dé nies par une union de boules. Néanmoins, la question de savoir quel ensemble de boules utiliser pour approximer une forme est non trivial, de telle sorte que ce travail aborde deux problèmes liés. Pour les présenter, par conformation moléculaire, nous entendons un modèle dé ni par un ensemble ni de boules. La premier problème, ou selection de diversité géométrique, consiste à choisir k conformations moléculaires parmi n, de façon à maximiser la diversité de l'ensemble choisi. Le second, ou approximation par défaut, consiste à approximer une molécule de n boules par k < n boules. Du point de vue théorique, nous montrons que les deux problèmes peuvent être traités avec une variante géométrique de max k-cover, les poids dépendant de la géométrie d'un arrangement surfacique ou volumique de sphères. La résolution de ces problèmes par un algorithme glouton permet d'avoir un facteur d'approximation borné inférieurement par 1 1=e dans certains cas. D'un point de vue appliqué, nous présentons une implémentation robuste de l'algorithme glouton pour l'approximation par défaut, laquelle incorpore (i) le calcul exact d'une triangulation de Delaunay dont les points ont des coordonnées qui sont des nombres algébriques de degré deux, (ii) le calcul exact de l'axe médian d'une union de boules, et (iii) une approximation certi ée du volume d'une union de boules. En particulier, nous montrons que des approximations précises de modèles moléculaires peuvent être obtenues en utilisant un nombre de boules 100 fois inférieur au nombre d'atomes, une propriété particulièrement séduisante pour la simulation d'environnement protéique dense.
Type de document :
Rapport
[Research Report] RR-8205, INRIA. 2013, pp.26
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00777892
Contributeur : Frederic Cazals <>
Soumis le : vendredi 18 janvier 2013 - 12:19:35
Dernière modification le : jeudi 11 janvier 2018 - 16:22:57
Document(s) archivé(s) le : vendredi 19 avril 2013 - 04:02:21

Fichier

RR-8205-greedy.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00777892, version 1

Collections

Citation

Frédéric Cazals, Tom Dreyfus, Sushant Sachdeva, Shah Nisarg. Greedy Geometric Optimization Algorithms for Collection of Balls. [Research Report] RR-8205, INRIA. 2013, pp.26. 〈hal-00777892〉

Partager

Métriques

Consultations de la notice

418

Téléchargements de fichiers

344