Home | Bookmarks | Papers | Blog |

Pankaj Agarwal, Sariel Har-Peled, Haim Kaplan, and Micha Sharir.

Let $\mathcal{C}= \{ C_1,...,C_n \}$ be a set of $n$ pairwise-disjoint convex sets of constant description complexity, and let $\pi$ be a probability density function (pdf for short) over the non-negative reals. For each $i$, let $K_i$ be the Minkowski sum of $C_i$ with a disk of radius $r_i$, where each $r_i$ is a random non-negative number drawn independently from the distribution determined by $\pi$. We show that the expected complexity of the union of $K_1, \ldots, K_n$ is $O( n^{1+\varepsilon} )$ for any $\varepsilon > 0$; here the constant of proportionality depends on $\varepsilon$ and on the description complexity of the sets in $\mathcal{C}$, but not on $\pi$. If each $C_i$ is a convex polygon with at most $s$ vertices, then we show that the expected complexity of the union is $O(s^2 n \log n)$.

Our bounds hold in the stronger model in which we are given an arbitrary multi-set $R=\{r_1,\ldots, r_n \}$ of expansion radii, each a non-negative real number. We assign them to the members of $\mathcal{C}$ by a random permutation, where all permutations are equally likely to be chosen; the expectations are now with respect to these permutations.

We also present an application of our results to a problem that arises in analyzing the vulnerability of a network to a physical attack.

PDF.

Last modified: Mon Oct 21 19:52:56 CDT 2013