In this note, we shall consider constant factor approximation algorithms for a variation of the discrete piercing set problem for unit disks. Here a set of points P is given; the objective is to choose minimum number of points inP to pierce all the disks of unit radius centered at the points in P . We rst propose a very simple algorithm that produces a 14-factor approximation result in O(n logn) time. Next, we improve the approximation factor to 4 and then to 3. Both algorithms run in polynomial time.
['Minati De', 'Gautam Das', 'Subhas C. Nandy']
Approximation Algorithms for the Discrete Piercing Set Problem for Unit Disks