Skip to Main content Skip to Navigation

Greedy Geometric Optimization Algorithms for Collection of Balls

Abstract : Modeling 3D objects with balls is routine for two reasons: on the one hand, the medial axis transform allows representing a solid object as a union of medial balls; on the other hand, selected shapes, and molecules in particular, are naturally represented by collections of balls. Yet, the problem of choosing which balls are best suited to approximate a given shape is a non trivial one. This paper addresses two problems in this realm. The first one, conformational diversity selection, consists of choosing $k$ molecular conformations amidst $n$, so as to maximize the geometric diversity of the $k$ conformers. The second one, inner approximation, consists of approximating a molecule of $n$ balls with $k$ balls. On the theoretical side, we demonstrate that for both problems, a geometric generalization of max $k$-cover applies, with weights depending on the cells of a surface or volumetric arrangement. Tackling these problems with greedy strategies, it is shown that the $1-1/e$ bound known in combinatorial optimization applies in some cases but not all. On the applied side, we present a robust and effective implementation of the greedy algorithm for the inner approximation problem, which incorporates the calculation of the exact Delaunay triangulation of a points whose coordinates are degree two algebraic number, of the medial axis of a union of balls, and of a certified estimate of the volume of a union of balls. In particular, we show that the inner approximation of complex molecules yields accurate coarse-grain models with a number of balls 100 times smaller than the number of atoms, a key requirement to simulate crowded protein environments.
Document type :
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Frederic Cazals Connect in order to contact the contributor
Submitted on : Friday, January 18, 2013 - 12:19:35 PM
Last modification on : Saturday, June 25, 2022 - 11:09:40 PM
Long-term archiving on: : Friday, April 19, 2013 - 4:02:21 AM


Files produced by the author(s)


  • HAL Id : hal-00777892, version 1



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⟩



Record views


Files downloads