ABSTRACT

Geometric covering problems deals with covering some points in geometric space with geometric shapes. These problems have many applications such as finding the locations of emergency facilities to be fair for all the clients, placing the wireless sensors or antennas to cover some targets, and image processing [1]. Examples of geometric shapes that have been studied more are disks and squares that are unit balls in (R 2, l 2) and (R 2, l ) metric spaces, respectively. The covering with unit balls problem is defined as follows: Given a set of points in (Rd, lp ) metric space, find the minimum number of unit balls of that metric to cover all the points. The problem is NP-hard as it generalizes the covering by disks problem [2]. Different constraints have been added to the problem and new problems have been introduced. In the current chapter, we survey the approximation algorithms for the covering with unit balls problem and some of its variants.