Unit disk cover problem in 2D

In this paper we consider the discrete unit disk cover problem and the rectangular region cover problem as follows:(i) Given a set PP of points and a set DD of unit disks in the plane such that ∪d∈Dd∪d∈Dd covers all the points in PP, select minimum cardinality subset D⁎⊆DD⁎⊆D such that each point in PP is covered by at least one disk in D⁎D⁎.(ii) Given a rectangular region RR and a set DD of unit disks in the plane such that R⊆∪d∈DdR⊆∪d∈Dd, select minimum cardinality subset D⁎⁎⊆DD⁎⁎⊆D such that each point of a given rectangular region RR is covered by at least one disk in D⁎⁎D⁎⁎.For the first problem, we propose a (9+ϵ)(9+ϵ)-approximation algorithm in O(m3(1+6ϵ)nlog⁡n) time for 0<ϵ≤60<ϵ≤6. The approximation factor of previous best known practical algorithm was 15 (Fraser and López-Ortiz (2012) [12]). For the second problem, we propose (i) a (9+ϵ)(9+ϵ)-approximation algorithm in O(m5+18ϵlog⁡m) time for 0<ϵ≤60<ϵ≤6, and (ii) a 2.25-approximation algorithm in reduce radius setup, improving previous 4-approximation result in the same setup (Funke et al. (2007) [11]).Our solution of the discrete unit disk cover problem is based on a polynomial time approximation scheme (PTAS) for the subproblem line separable discrete unit disk cover  , where all the points in PP are on one side of a line and covered by the union of the disks centered on the other side of that line.