Panos Giannopoulos, Christian Knauer, Günter Rote, and Daniel
Fixed-parameter 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,
We study the parameterized complexity of several stabbing problems. We show
that the (decision) problem of stabbing a set of axis-parallel unit squares
with k axis-parallel lines is W-hard with respect to k,
and thus, not fixed-parameter tractable unless W=FPT. When the lines can
have arbitrary directions, it is even W-hard for disjoint squares. For
stabbing disjoint unit squares with axis-parallel lines, we show that the
problem is fixed-parameter 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-hard with respect to the dimension d.
Last update: June 4, 2013.