An improved algorithm for computing the volume of the union of cubes
Pankaj K. Agarwal · 2010
Let C be a set of n axis-aligned cubes in ℜ3, and let U(C) denote the union of C. We present an algorithm that computes the volume of U(C) in time O(n polylog(n)). The previously best known algorithm takes O(n4/3 log2 n) time.