2017/04/23 by Shimin Li, Haitao Wang, Li, Shimin +1
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1704.06870
openalex publication_date 2017/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(n3log n)-time algorithm was given for the case m=1. In this paper, we propose an O(n2log nlog log n+nmlog m)-time algorithm for a more general setting with any m≥ 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(nlog n)-time algorithm was known for the case m=1. We present an algorithm of O(mlog m+nlog m log n) time for any m≥ 1. These problems may have applications in mobile sensor barrier coverage in wireless sensor networks.