Union of random Minkowski sums and network vulnerability analysis

DOI10.1007/S00454-014-9626-1zbMATH Open1302.52023arXiv1310.5647OpenAlexW1968547693MaRDI QIDQ471144FDOQ471144

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)

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. %

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

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

zbMATH Keywords

arrangementstochastic modelMinkowski sumnetwork vulnerability

Mathematics Subject Classification ID

Combinatorial complexity of geometric structures (52C45)

Cites Work

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

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
• Title not available (Why is that?)
• From proximity to utility: a Voronoi partition of Pareto optima
• Linear expected complexity for directional and multiplicative Voronoi diagrams
• Union of random minkowski sums and network vulnerability analysis
• 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)