Fixed-parameter tractability and lower bounds for stabbing problems

Details Fixed-parameter tractability and lower bounds for stabbing problems Fixed-parameter tractability and lower bounds for stabbing problems

2009-06-21

arxiv.org/abs/0906.3896v1

Computer Science

Computational Geometry

Based on the MSc. Thesis of Daniel Werner, Free University Berlin, Berlin, Germany

Scientific paper

We study the following general stabbing problem from a parameterized complexity point of view: Given a set $\mathcal S$ of $n$ translates of an object in $\Rd$, find a set of $k$ lines with the property that every object in $\mathcal S$ is ''stabbed'' (intersected) by at least one line. We show that when $S$ consists of axis-parallel unit squares in $\Rtwo$ 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 $\Rtwo$ 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 $\Rd$ can be stabbed by one line is W[1]--hard with respect to the dimension $d$.

Affiliated with

Also associated with

No associations

Rating

Fixed-parameter tractability and lower bounds for stabbing problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fixed-parameter tractability and lower bounds for stabbing problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fixed-parameter tractability and lower bounds for stabbing problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-494695