Algorithm to compute the volume of a finite union of overlapping balls?

153 Views Asked by At

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?

1

There are 1 best solutions below

1
On

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.