# Greedy Geometric Optimization Algorithms for Collection of Balls

1 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Keywords :
Document type :
Reports
Complete list of metadata

Cited literature [34 references]

https://hal.inria.fr/hal-00777892
Contributor : Frederic Cazals <>
Submitted on : Friday, January 18, 2013 - 12:19:35 PM
Last modification on : Thursday, August 22, 2019 - 12:10:38 PM
Long-term archiving on: : Friday, April 19, 2013 - 4:02:21 AM

### File

RR-8205-greedy.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00777892, version 1

### 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⟩

Record views