Computing the volume of the union of cubes
Pankaj K. Agarwal, Haim Y. Kaplan, Micha Sharir · 2007
Let C be a set of n axis-aligned cubes in R3, and let U(C) denote the union of C. We present an algorithmthat can compute the volume of U(C) in time O(n4/3 log n). The previously best known algorithm, by Overmars and Yap, computes the volume of the union ofany n axis-aligned boxes in R3 in O(n3/2log n) time.