The Within-Strip Discrete Unit Disk Cover Problem I,II

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 exists 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 height. An optimal solution to the WSDUDC problem is a set of disks of minimum cardinality that covers all points in the input set. We describe a range of approximation algorithms for the problem, including 4- and 3-approximate algorithms which apply for strips of height 2 2/3 ≈ 0.94 and 0.8 units respectively, as well as a general scheme for any strip with less than unit height. We prove that the WSDUDC problem is NP-complete on strips of any fixed height, 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 height. Finally, we discuss how these results may be applied to known DUDC approximation algorithms