Unit Disk Cover for Massive Point Sets

Publications

Unit Disk Cover for Massive Point Sets

Author : Dr Anirban Ghosh

Year : 2019

Publisher : Springer

Source Title : Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Document Type :

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.