License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.10
URN: urn:nbn:de:0030-drops-90147
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9014/
Agarwal, Pankaj K. ;
Kaplan, Haim ;
Sharir, Micha
Union of Hypercubes and 3D Minkowski Sums with Random Sizes
Abstract
Let T={triangle_1,...,triangle_n} be a set of of n pairwise-disjoint triangles in R^3, and let B be a convex polytope in R^3 with a constant number of faces. For each i, let C_i = triangle_i oplus r_i B denote the Minkowski sum of triangle_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+epsilon), for any epsilon > 0; the constant of proportionality depends on epsilon and the complexity of B. The worst-case bound can be Theta(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 2r_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, we show that the expected complexity of the union of the hypercubes is O(n^floor[d/2] log n) and the bound improves to O(n^floor[d/2]) if the scaling factors are chosen from a "well-behaved" pdf. The worst-case bounds are Theta(n^2) in R^3, and Theta(n^{ceil[d/2]}) in higher dimensions.
BibTeX - Entry
@InProceedings{agarwal_et_al:LIPIcs:2018:9014,
author = {Pankaj K. Agarwal and Haim Kaplan and Micha Sharir},
title = {{Union of Hypercubes and 3D Minkowski Sums with Random Sizes}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {10:1--10:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9014},
URN = {urn:nbn:de:0030-drops-90147},
doi = {10.4230/LIPIcs.ICALP.2018.10},
annote = {Keywords: Computational geometry, Minkowski sums, Axis-parallel cubes, Union of geometric objects, Objects with random sizes}
}
|
Keywords: |
|
Computational geometry, Minkowski sums, Axis-parallel cubes, Union of geometric objects, Objects with random sizes |
|
Collection: |
|
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.07.2018 |
