The geometric set cover problem is the special case of the set cover problem in geometric settings. The input is a range space formula_1 where formula_2 is a universe of points in formula_3 and formula_4 is a family of subsets of formula_2 called "ranges", defined by the intersection of formula_2 and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a "minimum-size" subset formula_7 of ranges such that every point in the universe formula_2 is covered by some range in formula_9.
Given the same range space formula_10, a closely related problem is the geometric hitting set problem, where the goal is to select a "minimum-size" subset formula_11 of points such that every range of formula_4 has nonempty intersection with formula_13, i.e., is "hit" by formula_13.
In the one-dimensional case, where formula_2 contains points on the real line and formula_4 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 formula_4 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.
Approximation algorithms.
The greedy algorithm for the general set cover problem gives formula_18 approximation, where formula_19. 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 formula_20-approximate set cover/hitting set for a range space formula_10 with constant VC-dimension can be computed in polynomial time, where formula_22 denotes the size of the optimal solution. The approximation ratio can be further improved to formula_23 or formula_24 when formula_4 is induced by axis-parallel rectangles or disks in formula_26, respectively.
Near-linear-time algorithms.
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 formula_27 time. For example, their algorithms computes an formula_23-approximate hitting set in formula_29 time for range spaces induced by 2D axis-parallel rectangles; and it computes an formula_24-approximate set cover in formula_31 time for range spaces induced by 2D disks.
References.
 ;templatestyles src="Reflist/styles.css" / ;