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

Let \(\mathcal {C}\) $\mathcal{C}$ be a set of n axis-aligned cubes of arbitrary sizes in \({\mathbb R}^3\) ${\mathbb{R}}^3$ in general position. Let \(\mathcal {U}:=\mathcal {U}(\mathcal {C})\) $\mathcal{U}:=\mathcal{U}(\mathcal{C})$ be their union, and let \(\kappa \) $\kappa$ be the number of vertices on \(\partial \mathcal {U}\) $\partial \mathcal{U}$ ; \(\kappa \) $\kappa$ can vary between O(1) and \(\Theta (n^2)\) $\mathrm{\Theta }(n^2)$ . We present a partition of \(\mathop {\textrm{cl}}({\mathbb R}^3\setminus \mathcal {U})\) $\text{cl}({\mathbb{R}}^3\backslash \mathcal{U})$ into \(O(\kappa \log ^4 n)\) $O(\kappa {log}^{4}n)$ axis-aligned boxes with pairwise-disjoint interiors that can be computed in \(O(n \log ^2 n + \kappa \log ^6 n)\) $O(n{log}^{2}n+\kappa {log}^{6}n)$ time if the faces of \(\partial \mathcal {U}\) $\partial \mathcal{U}$ are pre-computed. We also show that a partition of size \(O(\sigma \log ^4 n + \kappa \log ^2 n)\) $O(\sigma {log}^{4}n+\kappa {log}^{2}n)$ , where \(\sigma \) $\sigma$ is the number of input cubes that appear on \(\partial \mathcal {U}\) $\partial \mathcal{U}$ , can be computed in \(O(n \log ^2 n + \sigma \log ^8 n + \kappa \log ^6 n)\) $O(n{log}^{2}n+\sigma {log}^{8}n+\kappa {log}^{6}n)$ time if the faces of \(\partial \mathcal {U}\) $\partial \mathcal{U}$ are pre-computed. The complexity and runtime bounds improve to \(O(n\log n)\) $O(nlogn)$ if all cubes in \(\mathcal {C}\) $\mathcal{C}$ are congruent and the faces of \(\partial \mathcal {U}\) $\partial \mathcal{U}$ are pre-computed. Finally, we show that if \(\mathcal {C}\) $\mathcal{C}$ is a set of arbitrary axis-aligned boxes in \({\mathbb R}^3\) ${\mathbb{R}}^3$ , then a partition of \(\mathop {\textrm{cl}}({\mathbb R}^3\setminus \mathcal {U})\) $\text{cl}({\mathbb{R}}^3\backslash \mathcal{U})$ into \(O(n^{3/2}+\kappa )\) $O(n^{3/2}+\kappa )$ boxes can be computed in time \(O((n^{3/2}+\kappa )\log n)\) $O((n^{3/2}+\kappa )logn)$ , where \(\kappa \) $\kappa$ is, as above, the number of vertices in \(\mathcal {U}(\mathcal {C})\) $\mathcal{U}(\mathcal{C})$ , which now can vary between O(1) and \(\Theta (n^3)\) $\mathrm{\Theta }(n^3)$ .