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