Improved PTASs for convex barrier coverage (Q5896869)

Consider the problem when one uses mobile sensors to protect a region by monitoring its boundary and detecting intruders. Then, given \(n\) sensors in the interior of a planar connected region \(R\), we can consider the problem of moving the sensors to \(R\)'s boundary to form a barrier in the sense that every point on \(R\)'s boundary is covered by one of the sensors. The objective is to minimize the total travel distance of these sensors. In this paper, the cases where \(R\) is either a circle or a convex polygon are considered. A PTAS for the circle case is presented and it is explained how to overcome the main difficulties that arise when trying to adapt it to the convex polygon case. The proposed PTASs are significantly faster than the previously proposed ones. Moreover, the proposed PTASs provide efficient solutions to problems that are equivalent to the circle-restricted and line-restricted Weber problems. Thus, the efficient PTASs for these Weber problems are also devised.