The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space Σ = ( X , R ) where X is a universe of points in R d and R is a family of subsets of X called ranges, defined by the intersection of X and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset C ⊆ R of ranges such that every point in the universe X is covered by some range in C .
Given the same range space Σ , a closely related problem is the geometric hitting set problem, where the goal is to select a minimum-size subset H ⊆ X of points such that every range of R has nonempty intersection with H , i.e., is hit by H .
In the one-dimensional case, where X contains points on the real line and R is defined by intervals, both the geometric set cover and hitting set problems can be solved in polynomial time using a simple greedy algorithm. However, in higher dimensions, they are known to be NP-complete even for simple shapes, i.e., when R is induced by unit disks or unit squares.The discrete unit disc cover problem is a geometric version of the general set cover problem which is NP-hard.
Many approximation algorithms have been devised for these problems. Due to the geometric nature, the approximation ratios for these problems can be much better than the general set cover/hitting set problems. Moreover, these approximate solutions can even be computed in near-linear time.
The greedy algorithm for the general set cover problem gives O ( log n ) approximation, where n = max { | X | , | R | } . This approximation is known to be tight up to constant factor. However, in geometric settings, better approximations can be obtained. Using a multiplicative weight algorithm, Brönnimann and Goodrich showed that an O ( log O P T ) -approximate set cover/hitting set for a range space Σ with constant VC-dimension can be computed in polynomial time, where O P T ≤ n denotes the size of the optimal solution. The approximation ratio can be further improved to O ( log log O P T ) or O ( 1 ) when R is induced by axis-parallel rectangles or disks in R 2 , respectively.
Based on the iterative-reweighting technique of Clarkson and Brönnimann and Goodrich, Agarwal and Pan gave algorithms that computes an approximate set cover/hitting set of a geometric range space in O ( n p o l y l o g ( n ) ) time. For example, their algorithms computes an O ( log log O P T ) -approximate hitting set in O ( n log 3 n log log log O P T ) time for range spaces induced by 2D axis-parallel rectangles; and it computes an O ( 1 ) -approximate set cover in O ( n log 4 n ) time for range spaces induced by 2D disks.
