Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain

DOI10.1007/978-3-642-31155-0_16zbMATH Open1298.68276arXiv1207.6409OpenAlexW1988777116MaRDI QIDQ368758FDOQ368758

Authors: Danny Z. Chen, Yan Gu, Haitao Wang, Jian Li 

Publication date: 23 September 2013

Published in: Discrete \& Computational Geometry, Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Abstract: In this paper, we study the problem of moving $n$ sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an $O(n^{2}logn)$ time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes $O(n^2)$ time. We present an $O(nlogn)$ time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes $O(n)$ time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in $O(n)$ time, improving the previously best $O(n^2)$ time solution.

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

Recommendations

• Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain
• Barrier coverage with non-uniform lengths to minimize aggregate movements
• Algorithms for covering multiple barriers
• Algorithms for covering multiple barriers
• Barrier Coverage with Uniform Radii in 2D

zbMATH Keywords

optimizationalgorithmsbarrier coveragelinear barriermin-max sensor movement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication theory (94A05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Cites Work

• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Slowing down sorting networks to obtain faster sorting algorithms
• Optimal movement of mobile sensors for barrier coverage of a planar region
• Optimal point movement for covering circular regions
• New Algorithms for Barrier Coverage with Mobile Sensors
• An Optimal-Time Algorithm for Slope Selection
• Representing a functional curve by curves with fewer peaks

Cited In (24)

• On synchronization and orientation in distributed barrier coverage with relocatable sensors
• Algorithms for the line-constrained disk coverage and related problems
• “Green” Barrier Coverage with Mobile Sensors
• ``Green barrier coverage with mobile sensors
• Optimal Online and Offline Algorithms for Robot-Assisted Restoration of Barrier Coverage
• On the complexity of barrier resilience for fat regions and bounded ply
• On the displacement for covering a unit interval with randomly placed sensors
• Minimizing the total cost of barrier coverage in a linear domain
• Algorithms for covering multiple barriers
• Minimizing the Maximum Moving Cost of Interval Coverage
• Improved PTASs for convex barrier coverage
• New Algorithms for Barrier Coverage with Mobile Sensors
• Balanced splitting on weighted intervals
• Order preserving barrier coverage with weighted sensors on a line
• Optimizing Movement in Convex and Non-convex Path-Networks to Establish Connectivity
• Weak coverage of a rectangular barrier
• Maximizing Barrier Coverage Lifetime with Mobile Sensors
• Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements
• Optimal online and offline algorithms for robot-assisted restoration of barrier coverage
• Distributed algorithms for barrier coverage using relocatable sensors
• Optimizing movement in convex and non-convex path-networks to establish connectivity
• Optimal movement of mobile sensors for barrier coverage of a planar region
• Complexity of barrier coverage with relocatable sensors in the plane
• Minimizing the aggregate movements for interval coverage

This page was built for publication: Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain

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