Practical Discrete Unit Disk Cover Using an Exact Line-Separable 
Algorithm

by Alejandro Salinger

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' \subseteq D to cover P. This problem is NP-hard and the best 
previous practical solution is a 38-approximation algorithm by Carmi et 
al. 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. results in an O(m^2n^4) 
time 22-approximate solution to the discrete unit disk cover problem.

This is joint work with Francisco Claude, Gautam K. Das, Reza Dorrigiv, 
Stephane Durocher, Robert Fraser, Alejandro Lopez-Ortiz, and Bradford G. 
Nickerson.