An output-sensitive algorithm for computing the union of cubes and fat boxes in 3D
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).
Volume / Issue
International Standard Serial Number (ISSN)
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)