Union of random minkowski sums and network vulnerability analysis


Journal Article

Let C = {C1,⋯, Cn} be a set of n pairwise-disjoint convex s-gons, for some constant s, and let π be a probability density function (pdf) over the non-negative reals. For each i, let Ki be the Minkowski sum of Ci with a disk of radius ri, where each ri is a random non-negative number drawn independently from the distribution determined by π. We show that the expected complexity of the union of K1,⋯, Kn is O (n log n), for any pdf π; the constant of proportionality depends on s, but not on the pdf. Next, we consider the following problem that arises in analyzing the vulnerability of a network under a physical attack. Let G = (V, ε) be a planar geometric graph where ε is a set of n line segments with pairwise-disjoint relative interiors. Let φ: ℝ≥0 → [0,1] be an edge failure probability function, where a physical attack at a location x ∈ ℝ2 causes an edge e of E at distance r from x to fail with probability φ(r); we assume that φ is of the form 1 - Π(x), where Π is a cumulative distribution function on the non-negative reals. The goal is to compute the most vulnerable location for G, i.e., the location of the attack that maximizes the expected number of failing edges of G. Using our bound on the complexity of the union of random Minkowski sums, we present a near-linear Monte-Carlo algorithm for computing a location that is an approximately most vulnerable location of attack for G. Copyright 2013 ACM.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 2013

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 177 - 186

Digital Object Identifier (DOI)

  • 10.1145/2462356.2462398

Citation Source

  • Scopus