The discrete unit disk cover problem

Bob Fraser

Given a set P of n points and a set D of m unit radius disks in the plane, the discrete unit disk cover (DUDC) problem is to find a set D'⊆D of minimum cardinality such that D' covers P.

There have been a number of approximation algorithms which have appeared in the past decade which provide increasingly better approximation factors for DUDC. In this talk we will look at a few of these approaches and some specialized versions of the DUDC problem.