Decomposing the Complement of the Union of Cubes in Three Dimensions

Let C be a set of n axis-aligned cubes of arbitrary sizes in R 3 in general position. Let U := U(C) be their union, and let  be the number of vertices on @U;  can vary between O(1) and O(n 2 ). We show that cl(R 3 U) can be decomposed into O( log 4 n) axisaligned boxes with pairwise-disjoint interiors. Given a boundary representation of U, such a decomposition can be computed in O(n log 2 n +  log 6 n) time. We also show that a decomposition of size O( log 4 n +  log 2 n), where is the number of input cubes that appear on @U, can be computed in O(n log 2 n + log 8 n +  log 6 n) time. The complexity and runtime bounds improve to O(n log n) if all cubes in C are congruent.