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

DOI10.1016/J.COMGEO.2018.02.006zbMATH Open1443.68204arXiv1302.4707OpenAlexW2794302811MaRDI QIDQ1615674FDOQ1615674

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)

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

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

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

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)

Cites Work

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

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)