4

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?

valle
  • 864
  • 4
  • 15
  • Inclusion-exclusion comes to mind, but this will be extremely time-consuming without some symmetry. – David Handelman Sep 02 '17 at 23:16
  • How about Monte Carlo integration? – Liviu Nicolaescu Sep 02 '17 at 23:21
  • @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. – valle Sep 02 '17 at 23:54
  • A slightly more general question has been answered here https://mathoverflow.net/a/253979/31310 but the method might not be acceptable as computational geometry – Manfred Weis Sep 03 '17 at 12:52

1 Answers1

7

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."

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933