Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414763 | Computational Geometry | 2013 | 22 Pages |
We study the following general stabbing problem from a parameterized complexity point of view: Given a set SS of n translates of an object in RdRd, find a set of k lines with the property that every object in SS is “stabbed” (intersected) by at least one line.We show that when S consists of axis-parallel unit squares in R2R2 the (decision) problem of stabbing S with axis-parallel lines is W[1]-hard with respect to k (and thus, not fixed-parameter tractable unless FPT = W[1]) while it becomes fixed-parameter tractable when the squares are disjoint. We also show that the problem of stabbing a set of disjoint unit squares in R2R2 with lines of arbitrary directions is W[1]-hard with respect to k . Several generalizations to other types of objects and lines with arbitrary directions are also presented. Finally, we show that deciding whether a set of unit balls in RdRd can be stabbed by one line is W[1]-hard with respect to the dimension d.