Panos Giannopoulos, Christian Knauer, Günter Rote, and Daniel
Werner:
Fixedparameter tractability and lower bounds for stabbing problems

In: Abstracts of the 25th European Workshop on Computational Geometry
(EuroCG'09), Brussels, March 2009, pp. 281–284.
 Computational Geometry, Theory and Applications 46 (2013),
839–860. Special issue for the 25th European
Workshop on Computational Geometry (EuroCG'09). doi:10.1016/j.comgeo.2011.06.005,
arXiv:0906.3896 [cs.CG].
Abstract
We study the parameterized complexity of several stabbing problems. We show
that the (decision) problem of stabbing a set of axisparallel unit squares
with k axisparallel lines is W[1]hard with respect to k,
and thus, not fixedparameter tractable unless W[1]=FPT. When the lines can
have arbitrary directions, it is even W[1]hard for disjoint squares. For
stabbing disjoint unit squares with axisparallel lines, we show that the
problem is fixedparameter tractable by giving an algorithm that runs in
O(n log n) time for every fixed k. Deciding
whether a set of unit balls in d dimensions can be stabbed by one
line is W[1]hard with respect to the dimension d.
Last update: June 4, 2013.