Weak Coverage of a Rectangular Barrier

• Published in: Algorithmica 2020-04, Vol.82 (4), p.721-746
• Main Authors: Dobrev, Stefan, Kranakis, Evangelos, Krizanc, Danny, Lafond, Manuel, Maňuch, Ján, Narayanan, Lata, Opatrny, Jaroslav, Stacho, Ladislav
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Integers; Mathematics of Computing; Optimization; Position sensing; Sensors; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-019-00611-7

Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. Each sensor can monitor a circular area of specific diameter around its position, called the sensor diameter. Sensors are required to move to final locations so that they can there detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak barrier coverage of the region. We study three optimization problems related to the movement of sensors to achieve weak barrier coverage: minimizing the number of sensors moved (MinNum), minimizing the average distance moved by the sensors (MinSum), and minimizing the maximum distance moved by any sensor (MinMax). We give an O ( n 3 / 2 ) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions; in contrast the problem is shown to be NP-complete even for sensors of diameter 2 that are initially placed at integer positions. We show that the MinSum problem is solvable in O ( n log n ) time for the Manhattan metric and sensors of identical diameter (homogeneous sensors) in arbitrary initial positions, while it is NP-complete for heterogeneous sensors. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-complete.