Greedy Geometric Optimization Algorithms for Collection of Balls
type: Dataset
description: 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.
identifier: Report N°: RR-8205
issued: 2026-05-15T04:38:14.285619
language: en
modified: 2026-05-15T04:38:14.285624
contact point: Organization
  fn: CCSD
keyword: collection-of-balls
keyword: geometric-approximation
keyword: geometric-optimization
keyword: infoeu-reposemanticsreport
keyword: infoinfo-cgcomputer-science-cscomputational-geometry-cscg
keyword: inner-approximation
keyword: molecular-conformations
keyword: reports
landing page: https://inria.hal.science/hal-00777892

Greedy Geometric Optimization Algorithms for Collection of Balls
type: Distribution
format: HTML
issued: 2026-05-15T04:38:14.296350
modified: 2026-05-15T04:38:14.269069
access URL: https://inria.hal.science/hal-00777892

test_moissonnage_selune
type: Agent