Union of random Minkowski sums and network vulnerability analysis

DOI10.1007/S00454-014-9626-1MaRDI QIDQ471144zbMATH OpenOpenAlexFDO

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

Publication date 14 November 2014

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.5647

zbMATH Keywords

arrangementstochastic modelMinkowski sumnetwork vulnerability

Mathematics Subject Classification ID

Combinatorial complexity of geometric structures (52C45)

Abstract: Let $mathcalC=C_1,ldots,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 $mathcalC$, 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}nlogn)$. 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 $mathcalC$ 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. %

Recommendations

• Union of random minkowski sums and network vulnerability analysis
• Union of hypercubes and 3D Minkowski sums with random sizes
• Union of hypercubes and 3D Minkowski sums with random sizes
• Approximate unions of lines and Minkowski sums
• Algorithms – ESA 2004

Cites work

• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1947380 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• Add isotropic Gaussian kernels at own risk: more and more resilient modes in higher dimensions
• Applications of random sampling in computational geometry. II
• From proximity to utility: a Voronoi partition of Pareto optima
• Near-linear approximation algorithms for geometric hitting sets
• On Approximating the Depth and Related Problems
• On the boundary of the union of planar convex sets
• On the complexity of randomly weighted multiplicative Voronoi diagrams
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Realistic input models for geometric algorithms
• Relative (p, )-approximations in geometry
• State of the union (of geometric objects)
• Univariate Discrete Distributions

Cited in

(10)

• Minimum shared‐power edge cut
• Approximate convex intersection detection with applications to width and Minkowski sums
• Union of hypercubes and 3D Minkowski sums with random sizes
• Union of hypercubes and 3D Minkowski sums with random sizes
• scientific article; zbMATH DE number 7651184 (Why is no real title available?)
• From proximity to utility: a Voronoi partition of Pareto optima
• Union of random minkowski sums and network vulnerability analysis
• Linear expected complexity for directional and multiplicative Voronoi diagrams
• The number of holes in the union of translates of a convex set in three dimensions
• On the complexity of randomly weighted multiplicative Voronoi diagrams

This page was built for publication: Union of random Minkowski sums and network vulnerability analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q471144)