An output-sensitive algorithm for computing the union of cubes and fat boxes in 3D

Conference Paper

Let C be a set of n axis-aligned cubes of arbitrary sizes in ℝ3. Let U be their union, and let κ be the number of vertices on ∂U; κ can vary between O(1) and O(n2). We show that U can be computed in O(n log3 n + κ) time if C is in general position. The algorithm also computes the union of a set of fat boxes (i.e., boxes with bounded aspect ratio) within the same time bound. If the cubes in C are congruent or have bounded depth, the running time improves to O(n log2 n), and if both conditions hold, the running time improves to O(n log n).

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Steiger, A

Published Date

  • July 1, 2021

Published In

Volume / Issue

  • 198 /

International Standard Serial Number (ISSN)

  • 1868-8969

International Standard Book Number 13 (ISBN-13)

  • 9783959771955

Digital Object Identifier (DOI)

  • 10.4230/LIPIcs.ICALP.2021.10

Citation Source

  • Scopus