An approximation for covering points inside an orthogonal polygon with unit disks

We study a special case of the unit disk cover problem in which, for a given points set P of n points inside an orthogonal polygon, we seek to find the minimum number of unit disks that can cover all points inside the orthogonal polygon. We investigate the possibility of solving this problem with approximate approaches and present a ۴-approximation algorithm for this problem with O(n logn) running time.

کلیدواژه ها:

Covering problems ، approximation algorithms ، facility location ، NP-hard problems ، unit disk cover