Skip to main content
padlock icon - secure page this page is secure

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

Buy Article:

$52.00 + tax (Refund Policy)

Choosing balls that 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 FSFO. 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 11/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 Delaunay 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. Choosing balls which best approximate a 3D object is a nontrivial 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 FSFO. 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.
No References
No Citations
No Supplementary Data
No Article Media
No Metrics

Keywords: [Theory of Computation]: Design and analysis of algorithms; [Theory of Computation]: Randomness, geometry and discrete structures—Computational Geometry; [Theory of Computation]: Theory and algorithms for application domains; biological modelling; computational geometry; modelling

Document Type: Research Article

Publication date: September 1, 2014

  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
X
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more