Union of Hypercubes and 3D Minkowski Sums with Random Sizes

Journal Article (Journal Article)

Let T= { ▵1, … , ▵n} be a set of n triangles in R3 with pairwise-disjoint interiors, and let B be a convex polytope in R3 with a constant number of faces. For each i, let Ci= ▵i⊕ riB denote the Minkowski sum of ▵i with a copy of B scaled by ri> 0. We show that if the scaling factors r1, … , rn are chosen randomly then the expected complexity of the union of C1, … , Cn is O(n2+ε) , for any ε> 0 ; the constant of proportionality depends on ε and on the complexity of B. The worst-case bound can be Θ (n3). We also consider a special case of this problem in which T is a set of points in R3 and B is a unit cube in R3, i.e., each Ci is a cube of side-length 2 ri. We show that if the scaling factors are chosen randomly then the expected complexity of the union of the cubes is O(nlog 2n) , and it improves to O(nlog n) if the scaling factors are chosen randomly from a “well-behaved” probability density function (pdf). We also extend the latter results to higher dimensions. For any fixed odd value of d> 3 , we show that the expected complexity of the union of the hypercubes is O(n⌊d/2⌋log n) and the bound improves to O(n⌊d/2⌋) if the scaling factors are chosen from a “well-behaved” pdf. The worst-case bounds are Θ (n2) in R3, and Θ (n⌈d/2⌉) in higher odd dimensions.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Kaplan, H; Sharir, M

Published Date

  • June 1, 2021

Published In

Volume / Issue

  • 65 / 4

Start / End Page

  • 1136 - 1165

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/s00454-020-00274-0

Citation Source

  • Scopus