FPTAS for barrier covering problem with equal circles in 2D
share
In this paper, we consider a problem of covering a straight line segment using circles that are arbitrarily placed on a plane by moving their centers into a segment so that the segment is completely covered and the total length of the paths of movement of the circles would be minimal. In the case when the circles are equal, the complexity status of the problem is not known. In this paper, for the case when all circles are equal and touch each other in the cover, we propose an FPTAS with the complexity O(n^2.5_2 n/ε^2), where n is the number of circles.
READ FULL TEXT