Title: Algorithms for Covering Multiple Barriers,
Abstract: In this paper, we consider the problems for covering multiple intervals on a
line. Given a set $B$ of $m$ line segments (called "barriers") on a horizontal
line $L$ and another set $S$ of $n$ horizontal line segments of the same length
in the plane, we want to move all segments of $S$ to $L$ so that their union
covers all barriers and the maximum movement of all segments of $S$ is
minimized. Previously, an $O(n^3\log n)$-time algorithm was given for the case
$m=1$. In this paper, we propose an $O(n^2\log n\log \log n+nm\log m)$-time
algorithm for a more general setting with any $m\geq 1$, which also improves
the previous work when $m=1$. We then consider a line-constrained version of
the problem in which the segments of $S$ are all initially on the line $L$.
Previously, an $O(n\log n)$-time algorithm was known for the case $m=1$. We
present an algorithm of $O(m\log m+n\log m \log n)$ time for any $m\geq 1$.
These problems may have applications in mobile sensor barrier coverage in
wireless sensor networks.