0

Suppose I have finite list of $n$ 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?

a06e
  • 6,665

1 Answers1

1

Yes. there is an algorithm with time complexity $O(n)$. Details of implementation and algorithm step in this article: Computing the Volume of a Union of Balls: A Certified Algorithm which is implemented in CGAL. For example see this or this as a reference.

OmG
  • 3,138
  • Vorlume is now part of the Structural Bioinformatics Library: http://sbl.inria.fr/doc/Space_filling_model_surface_volume-user-manual.html – a06e Sep 03 '17 at 21:23