On the complexity of barrier resilience for fat regions and bounded ply

DOI10.1016/J.COMGEO.2018.02.006MaRDI QIDQ1615674zbMATH OpenOpenAlexFDO

Authors Matias Korman, Maarten Löffler, Rodrigo I. Silveira, Darren Strash

Publication date 31 October 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.4707, http://hdl.handle.net/2117/122214

zbMATH Keywords

approximation algorithmsparameterized complexitycoverageparameterized algorithmsbarrier resiliencebounded plyfat regions

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: In the emph {barrier resilience} problem (introduced by Kumar {em et al.}, Wireless Networks 2007), we are given a collection of regions of the plane, acting as obstacles, and we would like to remove the minimum number of regions so that two fixed points can be connected without crossing any region. In this paper, we show that the problem is NP-hard when the collection only contains fat regions with bounded ply $Delta$ (even when they are axis-aligned rectangles of aspect ratio $1:(1+varepsilon)$). We also show that the problem is fixed-parameter tractable (FPT) for unit disks and for similarly-sized $$-fat regions with bounded ply $Delta$ and $O(1)$ pairwise boundary intersections. Furthermore, we can use our FPT algorithm to construct an $(1+varepsilon)$-approximation algorithm that runs in $$ time, where $$.

Recommendations

• On the complexity of barrier resilience for fat regions
• Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience
• Approximating barrier resilience for arrangements of non-identical disk sensors
• A polynomial-time algorithm for computing the resilience of arrangements of ray sensors
• Approximation algorithms for the geometric firefighter and budget fence problems

Cites work

• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• Improved bounds on the union complexity of fat objects
• Multi-Commodity Network Flows
• Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience
• On Isolating Points Using Disks
• On the boundary of the union of planar convex sets
• On the complexity of barrier resilience for fat regions
• Parameterized graph separation problems
• Separators for sphere-packings and nearest neighbor graphs
• Simple and improved parameterized algorithms for multiterminal cuts
• Some simplified NP-complete graph problems
• State of the union (of geometric objects)
• The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
• The complexity of separating points in the plane

Cited in

(8)

• Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
• Minimum cuts in geometric intersection graphs
• Minimum shared‐power edge cut
• On the complexity of barrier resilience for fat regions
• The maximum exposure problem
• Hardness of minimum barrier shrinkage and minimum installation path
• How to navigate through obstacles?
• The Maximum Exposure Problem.

This page was built for publication: On the complexity of barrier resilience for fat regions and bounded ply

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