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 problem but only for the special case m=1. In this paper, we propose an O(n^2 log nlog log n+nm log m)-time algorithm for any m, which improves the previous work even for 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( (n + m) log(n + m )) time for any m . These problems may have applications in mobile sensor barrier coverage in wireless sensor networks.
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.
R
log
\log
D
problem but only for the special
R
log nlog log
\log n\log \log
R
log
\log
R
any m, which
a more general setting with any m\geq 1, which also
R
even for
when
R
log
\log
D
(n + m) log(n +
R
))
\log m+n\log m \log n)
R
.
\geq 1.