Greedy Geometric Algorithms for Collection of Balls, with Applications to Geometric Approximation and Molecular Coarse-Graining

Abstract : Choosing balls which best approximate a 3D object is a non trivial problem. To answer it, we first address the inner approximation problem, which consists of approximating an object FO defined by a union of n balls with k < n balls defining a region FS ⊂ FO. This solution is further used to construct an outer approximation enclosing the initial shape, and an interpolated approximation sandwiched between the inner and outer approximations. The inner approximation problem is reduced to a geometric generalization of weighted max k-cover, solved with the greedy strategy which achieves the classical 1 − 1/e lower bound. The outer approximation is reduced to exploiting the partition of the boundary of FO by the Apollonius Voronoi diagram of the balls defining the inner approximation. Implementation-wise, we present robust software incorporating the calculation of the exact Delau-nay triangulation of points with degree two algebraic coordinates, of the exact medial axis of a union of balls, and of a certified estimate of the volume of a union of balls. Application-wise, we exhibit accurate coarse-grain molecular models using a number of balls 20 times smaller than the number of atoms, a key requirement to simulate crowded cellular environments.
Type de document :
Article dans une revue
Computer Graphics Forum, Wiley, 2014, 33, pp.1 - 17. 〈10.1111/cgf.12270〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01110229
Contributeur : Frederic Cazals <>
Soumis le : mardi 27 janvier 2015 - 16:57:19
Dernière modification le : samedi 21 juillet 2018 - 14:12:01
Document(s) archivé(s) le : mardi 28 avril 2015 - 11:11:31

Fichier

greedy-balls-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Frédéric Cazals, Tom Dreyfus, S Sachdeva, N Shah. Greedy Geometric Algorithms for Collection of Balls, with Applications to Geometric Approximation and Molecular Coarse-Graining. Computer Graphics Forum, Wiley, 2014, 33, pp.1 - 17. 〈10.1111/cgf.12270〉. 〈hal-01110229〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

215