Near‐Linear Approximation Algorithms for Geometric Hitting Sets

Given a range space $(X,ℛ)$ , where $ℛ\subset 2^X$ , the hitting set problem is to find a smallest‐cardinality subset H⊆X that intersects each set in $ℛ$ . We present near‐linear‐time approximation algorithms for the hitting set problem in the following geometric settings: (i) $ℛ$ is a set of planar regions with small union complexity. (ii) $ℛ$ is a set of axis‐parallel d‐dimensional boxes in ℝ ^d . In both cases X is either the entire ℝ ^d , or a finite set of points in ℝ ^d . The approximation factors yielded by the algorithm are small; they are either the same as, or within very small factors off the best factors known to be computable in polynomial time.