Approximation algorithms for hitting objects with straight lines

Abstract

In the hitting set problem one is given m subsets of a finite set N and one has to find an X ⊂ N of minimum cardinality that "hits" (intersects) all of them. The problem is NP-hard. It is not known whether there exists a polynomial-time approximation algorithm for the hitting set problem with a finite performance ratio. Special cases of the hitting set problem are described for which finite performance ratios are guaranteed. These problems arise in a geometric setting. We consider special cases of the following problem: Given n compact subsets of Rd, find a set of straight lines of minimum cardinality so that each of the given subsets is hit by at least one line. The algorithms are based on several techniques of representing objects by points, not necessarily points on the objects, and solving (in some cases, only approximately) the problem of hitting the representative points. Finite performance ratios are obtained when the dimension, the number of types of sets to be hit and the number of directions of the hitting lines are bounded. © 1991.