Union of Hypercubes and 3D Minkowski Sums with Random Sizes

• Published in: Discrete & computational geometry 2021-06, Vol.65 (4), p.1136-1165
• Main Authors: Agarwal, Pankaj K., Kaplan, Haim, Sharir, Micha
• Format: Article
• Language: English
• Subjects: Combinatorics; Complexity; Computational Mathematics and Numerical Analysis; Cubes; Hypercubes; Mathematics; Mathematics and Statistics; Probability density functions; Scaling factors
• ISSN: 0179-5376; 1432-0444
• DOI: 10.1007/s00454-020-00274-0

Let T = { ▵ 1 , … , ▵ n } be a set of n triangles in R 3 with pairwise-disjoint interiors, and let B be a convex polytope in R 3 with a constant number of faces. For each  i , let C i = ▵ i ⊕ r i B denote the Minkowski sum of ▵ i with a copy of B scaled by r i > 0 . We show that if the scaling factors r 1 , … , r n are chosen randomly then the expected complexity of the union of C 1 , … , C n is O ( n 2 + ε ) , for any ε > 0 ; the constant of proportionality depends on ε and on the complexity of  B . The worst-case bound can be  Θ ( n 3 ) . We also consider a special case of this problem in which T is a set of points in R 3 and B is a unit cube in  R 3 , i.e., each C i is a cube of side-length  2 r i . We show that if the scaling factors are chosen randomly then the expected complexity of the union of the cubes is O ( n log 2 n ) , and it improves to O ( n log 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 Θ ( n 2 ) in  R 3 , and Θ ( n ⌈ d / 2 ⌉ ) in higher odd dimensions.