Abstract
Given a set of points in the plane, the Unit Disk Cover (UDC) problem asks to compute the minimum number of unit disks required to cover the points, along with a placement of the disks. The problem is NP-Hard and several approximation algorithms have been designed over the last three decades. In this paper, we experimentally compare practical performances of some of these algorithms on massive point sets. The goal is to investigate which algorithms run fast and give good approximation in practice. We present an elementary online 7-approximation algorithm for UDC which runs in (formula presented) time on average and is easy to implement. In our experiments with both synthetic and real-world massive point sets, we have observed that this algorithm is up to 61.63 times and at least 2.9 times faster than the existing algorithms implemented in this paper. It gave 2.7-approximation in practice for the point sets used in our experiments. In our knowledge, this is the first work which experimentally compares the existing algorithms for UDC.