I need to calculate the overlap between two 3D volumes each of which is described as the union of a set of (possibly overlapping) spheres. If the two sets of spheres are S_i (with radius r_i and center at c_i) and S_j (radius r_j and center at c_j); consider the two combined volumes in 3D given by union(S_i) and union(S_j), and then calculate volume(intersection(union(S_i), union(S_j))).

Is there a reasonably fast algorithm for this?

Also: is there a fast approximate algorithm with a bound on the max error?

(Part of what makes that tricky is that spheres within each set can overlap in arbitrary ways; most of the time they overlap a little - let's say for the typical sphere in one set, there are a few other spheres in the same set that overlap it by a few % of its volume; but they could also overlap by a lot more, and in principle the same point in 3D could be in the interior of a lot more than two spheres in the same set, so an exact solution would have to consider 3-way, 4-way and so on up to n-way overlapped regions. A fast approximate solution doesn't necessarily have to do that)