Union of Random Minkowski Sums and Network Vulnerability Analysis

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

Research output: Contribution to journalArticlepeer-review


Let (Formula Prseented.) be a set of n pairwise-disjoint convex sets of constant description complexity, and let π be a probability density function (density for short) over the non-negative reals. For each i, let (Formula Prseented.) be the Minkowski sum of (Formula Prseented.) with a disk of radius (Formula Prseented.), where each (Formula Prseented.) is a random non-negative number drawn independently from the distribution determined by π. We show that the expected complexity of the union of (Formula Prseented.) is (Formula Prseented.) for any (Formula Prseented.) here the constant of proportionality depends on (Formula Prseented.) and the description complexity of the sets in C, but not on π. If each (Formula Prseented.) is a convex polygon with at most s vertices, then we show that the expected complexity of the union is (Formula Prseented.). Our bounds hold in a more general model in which we are given an arbitrary multi-set (Formula Prseented.) of expansion radii, each a non-negative real number. We assign them to the members of 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.

Original languageEnglish (US)
Pages (from-to)551-582
Number of pages32
JournalDiscrete and Computational Geometry
Issue number3
StatePublished - Sep 1 2014


  • Arrangement
  • Minkowski sum
  • Network vulnerability
  • Stochastic model

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Union of Random Minkowski Sums and Network Vulnerability Analysis'. Together they form a unique fingerprint.

Cite this