The Within-Strip Discrete Unit Disk Cover Problem

We investigate the Within-Strip Discrete Unit Disk Cover problem (WSDUDC), where one wishes to find a minimal set of unit disks from an input set D so that a set of points P is covered. Furthermore, all points and disk centres are located in a strip of height h, defined by a pair of parallel lines. We give a general approxi-mation algorithm which finds a 3d1/√1 − h2e-factor ap-proximation to the optimal solution. We also provide a 4-approximate solution given a strip where h ≤ 2√2/3, and a 3-approximation in a strip if h ≤ 4/5, improv-ing over the 6-approximation for such strips using the general scheme. Finally, we show that WSDUDC is NP-complete for a strip with any height h> 0.