Geometric set cover problem

The geometric set cover problem is the special case of the <a href="/facts/Set_cover_problem/MVzyBYs1">set cover problem</a> in geometric settings. The input is a range space 
 
 
 
 Σ
 =
 (
 X
 ,
 
 
 R
 
 
 )
 
 
 {\displaystyle \Sigma =(X,{\mathcal {R}})}
 
 where 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is a <a href="/facts/Universe_(mathematics)/v2oJnu4e">universe</a> of points in 
 
 
 
 
 
 R
 
 
 d
 
 
 
 
 {\displaystyle \mathbb {R} ^{d}}
 
 and 
 
 
 
 
 
 R
 
 
 
 
 {\displaystyle {\mathcal {R}}}
 
 is a family of subsets of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 called ranges, defined by the <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 and geometric shapes such as disks and axis-parallel rectangles. The goal is to select a minimum-size subset 
 
 
 
 
 
 C
 
 
 ⊆
 
 
 R
 
 
 
 
 {\displaystyle {\mathcal {C}}\subseteq {\mathcal {R}}}
 
 of ranges such that every point in the universe 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is covered by some range in 
 
 
 
 
 
 C
 
 
 
 
 {\displaystyle {\mathcal {C}}}
 
.
Given the same range space 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
, a closely related problem is the geometric hitting set problem, where the goal is to select a minimum-size subset 
 
 
 
 H
 ⊆
 X
 
 
 {\displaystyle H\subseteq X}
 
 of points such that every range of 
 
 
 
 
 
 R
 
 
 
 
 {\displaystyle {\mathcal {R}}}
 
 has nonempty intersection with 
 
 
 
 H
 
 
 {\displaystyle H}
 
, i.e., is hit by 
 
 
 
 H
 
 
 {\displaystyle H}
 
.
In the one-dimensional case, where 
 
 
 
 X
 
 
 {\displaystyle X}
 
 contains points on the <a href="/facts/Real_line/6eq42xX5">real line</a> and 
 
 
 
 
 
 R
 
 
 
 
 {\displaystyle {\mathcal {R}}}
 
 is defined by intervals, both the geometric set cover and hitting set problems can be solved in <a href="/facts/Time_complexity/77T62gmf">polynomial time</a> using a simple <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithm</a>. However, in higher dimensions, they are known to be <a href="/facts/NP-completeness/NFPv56DU">NP-complete</a> even for simple shapes, i.e., when 
 
 
 
 
 
 R
 
 
 
 
 {\displaystyle {\mathcal {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 <a href="/facts/NP-hardness/mQeNPv4R">NP-hard</a>.
Many <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithms</a> 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.

Geometric set cover problem open-in-new

Geometric set cover problem