Panos Giannopoulos, Christian Knauer, Günter Rote, and Daniel Werner:

Fixed-parameter tractability and lower bounds for stabbing problems

  1. In: Abstracts of the 25th European Workshop on Computational Geometry (EuroCG'09), Brussels, March 2009, pp. 281–284.
  2. 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 axis-parallel unit squares with k axis-parallel lines is W[1]-hard with respect to k, and thus, not fixed-parameter 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 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[1]-hard with respect to the dimension d.

  pdf file
other papers about this subject
Last update: June 4, 2013.