The Hitting Set Problem is a well-studied, NP-complete problem in combinatorial optimization. It can be formulated as follows: Given a finite ground set X and a collection R of its subsets, find a minimum-cardinality set H ⊆ X which intersects (hits) all sets in R. In this thesis we focus on special cases where X is a set of points in plane, and elements of R correspond to geometric objects. We describe different approximation techniques used for attacking these problems, namely LP-rounding, ε-nets, local search, as well as greedy algorithms.

In chapter 2, we describe three techniques for approximating the general hitting set problem: greedy, randomized rounding and ε-nets. In chapter 3, we describe several geometric instances of the problem. Section 3.1 describes the well-known interval hitting problem, that will be used in later sections for solving more difficult cases. Section 3.2 is about hitting sets of horizontal segments and vertical lines, where we give an approximation algorithm and a bound on the duality gap. The next two sections describe two useful approximation techniques, namely LP-rounding (section 3.3) and local search (section 3.4). Section 3.5 is about a special case of the art gallery problem, where guards have the so-called rook vision. The results in section 3.5 and the bounds on the duality gap in 3.2.2 are original.