Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235367] of Pankaj K. Agarwal

Papers Published

  1. 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. 177-186
    (last updated on 2018/11/13)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320