Math @ Duke

Publications [#235367] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kaplan, H; Sharir, M, Union of random minkowski sums and network vulnerability analysis,
Proceedings of the Annual Symposium on Computational Geometry
(2013),
pp. 177186
(last updated on 2018/11/13)
Abstract: Let C = {C1,⋯, Cn} be a set of n pairwisedisjoint convex sgons, for some constant s, and let π be a probability density function (pdf) over the nonnegative reals. For each i, let Ki be the Minkowski sum of Ci with a disk of radius ri, where each ri is a random nonnegative 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 pairwisedisjoint 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 nonnegative 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 nearlinear MonteCarlo algorithm for computing a location that is an approximately most vulnerable location of attack for G. Copyright 2013 ACM.


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

