## Abstract

Given a set D of m unit disks and a set P of n points in the plane, the discrete unit disk cover problem is to select a minimum cardinality subset*D'⊆D*to cover P. This problem is NP-hard [D. Johnson, 1982] and the best previous practical solution is a 38-approximation algorithm by [Carmi et al., 2007]. We first consider the line-separable discrete unit disk cover problem (the set of disk centers can be separated from the set of points by a line) for which we present an O(

*n(log n +m)*)-time algorithm that finds an exact solution.

Combining our line-separable algorithm with techniques from the algorithm of [Carmi et al., 2007] results in an O(

*m*) time 22-approximate solution to the discrete unit disk cover problem.

^{2}n^{4}