Math @ Duke

Publications [#337042] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kaplan, H; Sharir, M, Union of hypercubes and 3D minkowski sums with random sizes,
Leibniz International Proceedings in Informatics, Lipics, vol. 107
(July, 2018), ISBN 9783959770767 [doi]
(last updated on 2019/02/18)
Abstract: © Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir;. Let T = (1n) be a set of of n pairwisedisjoint triangles in R3, and let B be a convex polytope in R3with a constant number of faces. For each i, let Ci=iriB denote the Minkowski sum ofiwith a copy of B scaled by ri> 0. We show that if the scaling factors r1, . . ., rnare chosen randomly then the expected complexity of the union of C1, . . ., Cnis O(n2+ε), for any ε > 0; the constant of proportionality depends on ε and the complexity of B. The worstcase bound can be (n3). We also consider a special case of this problem in which T is a set of points in R3and B is a unit cube in R3, i.e., each Ciis a cube of sidelength 2ri. We show that if the scaling factors are chosen randomly then the expected complexity of the union of the cubes is O(n log2n), and it improves to O(n log n) if the scaling factors are chosen randomly from a “wellbehaved” 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 “wellbehaved” pdf. The worstcase bounds are (n2) in R3, and (nd/2) in higher dimensions.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

