Drone Placement for Optimal Barrier Coverage

A line segment (barrier) is specified on the plane, as well as the location of depots. Each sensor is able to travel a limited-length path, starting and ending at its depot. The part of the barrier along which the sensor moves is covered by this sensor. It is necessary to place some number of mobile sensors (drones) in each depot in order to cover the entire barrier with a minimum number of drones (MinNum), or to minimize the total length of paths traveled by drones (MinSum), or to minimize the maximum distance traveled by a drone (MinMax). Previously, the authors investigated a similar problem with an unlimited number of drones and, for its solution, proposed a pseudopolynomial algorithm depending on the length of the barrier L. In this paper, a generalized problem with a limited number of drones is considered and, to construct an optimal solution, we propose an algorithm with the same complexity. However, in the case of an unlimited number of drones, the new algorithm has complexity $$ L $$ times less than the previous one.