TR11-019 Authors: Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni

Publication: 11th February 2011 10:07

Downloads: 3283

Keywords:

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case of the set covering problem where the family of subsets given can be taken as a set of intersections of the straight line segments in $S$. Requiring that the given subsets can be interpreted geometrically this way is a major restriction on the input, yet we have shown that the problem is still strongly NP-complete. In light of this result, we studied the performance of two polynomial-time approximation algorithms which return segment coverings. We obtain certain theoretical results, and in particular we show that the performance ratio for each of these algorithms is unbounded, in general.