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 conned to a strip of xed 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 p 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 xed 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 xed height. Finally, we discuss how these results may be applied to known DUDC approximation algorithms.
['Robert Fraser', 'Alejandro L']
The Within-Strip Discrete Unit Disk Cover Problem