# Union of hypercubes and 3D minkowski sums with random sizes

Conference Paper

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

### Full Text

### Duke Authors

### Cited Authors

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

### Published Date

- July 1, 2018

### Published In

### Volume / Issue

- 107 /

### International Standard Serial Number (ISSN)

- 1868-8969

### International Standard Book Number 13 (ISBN-13)

- 9783959770767

### Digital Object Identifier (DOI)

- 10.4230/LIPIcs.ICALP.2018.10

### Citation Source

- Scopus