English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper, we study the problem of moving $$n$$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\log n)$$O(n2logn) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes $$O(n^2)$$O(n2) time. We present an $$O(n\log n)$$O(nlogn) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes $$O(n)$$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)$$O(n) time, improving the previously best $$O(n^2)$$O(n2) time solution.

Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain