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.
