4
$\begingroup$

Suppose I have finite list of $n$ 3-dimensional balls, specifying their positions and radii. The balls can have non-empty intersections.

Is there an algorithm to compute the volume of the region resulting from the union of all $n$ balls? How hard is this problem?

Is there a source code out there that does the computation already?

Improve this question
$\endgroup$
4
  • $\begingroup$ Inclusion-exclusion comes to mind, but this will be extremely time-consuming without some symmetry. $\endgroup$
    – David Handelman
    Commented Sep 2, 2017 at 23:16
  • $\begingroup$ How about Monte Carlo integration? $\endgroup$
    – Liviu Nicolaescu
    Commented Sep 2, 2017 at 23:21
  • $\begingroup$ @LiviuNicolaescu How exactly would that work? I sample a rectangular cube containing all the spheres? This can be expensive if the spheres are extended on a linear dimension not aligned with the axes. $\endgroup$
    – valle
    Commented Sep 2, 2017 at 23:54
  • $\begingroup$ A slightly more general question has been answered here mathoverflow.net/a/253979/31310 but the method might not be acceptable as computational geometry $\endgroup$
    – Manfred Weis
    Commented Sep 3, 2017 at 12:52

1 Answer 1

Reset to default
7
$\begingroup$

This impressive work was tested on ~60,000 models in the Protein Data Bank, computing the volume of the union of sometimes more than 50,000 atoms represented as balls of different radii. Implemented in C++:

Cazals, Frédéric, Harshad Kanhere, and Sébastien Loriot. "Computing the volume of a union of balls: A certified algorithm." ACM Transactions on Mathematical Software (TOMS) 38.1 (2011): 3. (ACM link.)

         

Their algorithm is based on the "decomposition of the volume of the union into convex regions, namely the restrictions of the balls to their regions in the power diagram. Theoretically, we establish a formula for the volume of a restriction, based on Gauss' divergence theorem. The proof being constructive, we develop the associated algorithm."

Improve this answer
$\endgroup$
3
  • $\begingroup$ I cannot find the source code of this. $\endgroup$
    – valle
    Commented Sep 3, 2017 at 8:26
  • 2
    $\begingroup$ @becko: I would write to the authors. In 2011 they were at: ABS-Algorithms, Biology, Structure, CRISAM-Inria Sophia Antipolis- Méditerranée, and IIT Bombay-Indian Institute of Technology. Here is Frédéric Cazals homepage. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 3, 2017 at 13:04
  • 1
    $\begingroup$ Thanks. I contacted them. Vorlume is now part of the Structural Bioinformatics Library: sbl.inria.fr/doc/… $\endgroup$
    – valle
    Commented Sep 3, 2017 at 20:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .