# Decomposing the complement of the union of cubes in three dimensions

Conference Paper

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 O(n2). We show that cl(R3 \ U) can be decomposed into O(κ log4 n) axis-aligned boxes with pairwise-disjoint interiors. Given a boundary representation of U, such a decomposition can be computed in O(n log2 n + κ log6 n) time. We also show that a decomposition of size O(σ log4 n + κ log2 n), where σ is the number of input cubes that appear on ∂U, can be computed in O(n log2 n + σ log8 n + κ log6 n) time. The complexity and runtime bounds improve to O(n log n) if all cubes in C are congruent.

### Duke Authors

### Cited Authors

- Agarwal, PK; Sharir, M; Steiger, A

### Published Date

- January 1, 2021

### Published In

- Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

### Start / End Page

- 1425 - 1444

### International Standard Book Number 13 (ISBN-13)

- 9781611976465

### Citation Source

- Scopus