Approximation algorithms for the unit disk cover problem in 2D and 3D (Q680146): Difference between revisions

The authors deal with the problem of unit disk cover (UDC), i.e., given a set \(P\) of \(n\) points in the plane we search for the minimum number of disks of prescribed radius \(r\), which cover all points of \(P\). Firstly, the authors consider the UDC problem in the Euclidean norm and the radii of the disks is \(1\). They propose a \(4\)-approximation algorithm that runs in \(O(n \log n + n t(d))\) time, where \(t(d)\) is the time for computing the distance between point and set. Using appropriate data structures the proposed algorithm can be implemented to run in \(O(n \log^2 n)\) time and use \(O(n)\) space. Next, the authors improve the time complexity of the algorithm by the use of sweep-line and obtain an algorithm that runs in \(O(n \log n)\) time and uses the \(O(n)\) space. Then, they extend the algorithm from Euclidean metric to the \(L_t\)-norm for \(t \geq 1\). For various values of \(t\) the authors obtain different approximation algorithms. For \(t \in [1, 2]\) they obtain a \(5\)-approximation algorithm, for \(t \geq 2\) a \(6\)-approximation algorithm, whereas for \(t = \infty\) they obtain a \(2\)-approximation algorithm. All the algorithms run in \(O(n \log n)\) time. Finally, the authors consider a unit ball cover, i.e., given a set \(P\) of \(n\) points in 3D space we search for the minimum number of unit balls which cover all points of \(P\). They show how to extend the 2D version of the UDC algorithm to the 3D case. The proposed algorithm is a \(12\)-approximation algorithms that runs in \(O(n \log n)\) time.