The within-strip discrete unit disk cover problem

We present a study of the Within-Strip Discrete Unit Disk Cover (WSDUDC) problem, which is a restricted version of the Discrete Unit Disk Cover (DUDC) problem. For the WSDUDC problem, there exist a set of points and a set of unit disks in the plane, and the points and disk centres are confined to a strip of fixed width. An optimal solution to the WSDUDC problem is a subset of the disks of minimum cardinality that covers all points in the input set. We describe two approximation algorithms for the problem: a 3-approximate algorithm which applies for strips of width at most 0.8 units, and a general scheme for any strip with less than unit width. We prove that the WSDUDC problem is NP-hard on strips of any fixed width, which is our most interesting result from a theoretical standpoint. The result is also quite surprising, since a number of similar problems are tractable on strips of fixed width. Finally, we discuss how these results may be applied to known DUDC approximation algorithms.