Decomposing the Complement of the Union of Cubes and Boxes in Three Dimensions

Let C be a set of n axis-aligned cubes of arbitrary sizes in R3 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 Θ(n2). We present a partition of cl(R3\U) into O(κlog4n) axis-aligned boxes with pairwise-disjoint interiors that can be computed in O(nlog2n+κlog6n) time if the faces of ∂U are pre-computed. We also show that a partition of size O(σlog4n+κlog2n), where σ is the number of input cubes that appear on ∂U, can be computed in O(nlog2n+σlog8n+κlog6n) time if the faces of ∂U are pre-computed. The complexity and runtime bounds improve to O(nlogn) if all cubes in C are congruent and the faces of ∂U are pre-computed. Finally, we show that if C is a set of arbitrary axis-aligned boxes in R3, then a partition of cl(R3\U) into O(n3/2+κ) boxes can be computed in time O((n3/2+κ)logn), where κ is, as above, the number of vertices in U(C), which now can vary between O(1) and Θ(n3).

Duke Scholars

Author Alexander Steiger Computer Science