Fixed-parameter tractability and lower bounds for stabbing problems

DOI10.1016/J.COMGEO.2011.06.005MaRDI QIDQ359746zbMATH OpenOpenAlexFDO

Authors Panos Giannopoulos, Christian Knauer, Günter Rote, Daniel Werner

Publication date 22 August 2013

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.3896, http://www.sciencedirect.com/science/article/pii/S0925772111000502

zbMATH Keywords

algorithmcomplexityfixed-parameter tractabilitygeometric stabbingminimum enclosing cylinder

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Abstract: We study the following general stabbing problem from a parameterized complexity point of view: Given a set $mathcalS$ of $n$ translates of an object in $Rd$, find a set of $k$ lines with the property that every object in $mathcalS$ 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$.

Review text

The authors study the parametrized complexity of several instances of the general geometric stabbing (or hitting) problem: Given a set \(S\) of \(n\) translates of an object in \({\mathbb R}^d\) and a positive integer \(k\), select at most \(k\) lines such that every object is intersected by at least one of the selected lines. This is a typical algorithmical problem the parametrized complexity theory deals with (see [\textit{J. Flum} and \textit{M. Grohe}, Parametrized complexity theory. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer (2006; Zbl 1143.68016)]): when the input can be broken into two parts one having length \(k\) (the number of selected lines, the parameter) and the other having length \(n\) (the number of copies of the translated object), with the expectation that \(k<<n\). The class of problems solvable by algorithms running in time \(f(k)\cdot poly(n)\), where \(f\) is a computable function, is called the class of fixed-parameter tractable problems. The first level in the hierarchy of fixed-parameter intractability is denoted by \(W(1)\).NEWLINENEWLINESome results are proven in the negative sense: let \(O\) be a connected object in the plane, if the stabbing lines are to parallel to two different directions that are part of the input, the problem of stabbing a set of disjoint translates of \(O\) with \(k\) lines is \(W(1)\)-hard with respect to \(k\), in general. The same happens when the lines have arbitrary directions. Such results generalize those contained in the paper by \textit{M. Dom} et al. [Algorithmica 62, No. 1--2, 564--594 (2012; Zbl 1236.68083)].NEWLINENEWLINEIn the positive sense two instances are shown to be fixed-parameter tractable: stabbing a set of \(n\) axis-parallel disjoint unit squares with \(k\) axis-parallel lines and, stabbing a set of \(n\) translates of a planar connected object with \(k\) lines with respect to \(k\), the number of lines' directions and the maximum number of objects that can be simultaneously intersected by two lines with different directions.NEWLINENEWLINEFinally, the higher-dimensional problem of stabbing \(n\) unit balls in \({\mathbb R}^d\) with one line is shown to be \(W(1)\)-hard with respect to \(d\).

Recommendations

• The parameterized complexity of stabbing rectangles
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
• New results on a family of geometric hitting set problems in the plane
• The parameterized complexity of some geometric problems in unbounded dimension

Cites work

• A (slightly) faster algorithm for klee's measure problem
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• Algorithms – ESA 2005
• Approximate clustering via core-sets
• Approximating the Radii of Point Sets
• Approximation algorithms for hitting objects with straight lines
• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
• Constant approximation algorithms for rectangle stabbing and related problems
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Covering things with things
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing
• Geometric clustering, fixed-parameter tractability and lower bounds with respect to the dimension
• scientific article; zbMATH DE number 5764822 (Why is no real title available?)
• Linear FPT reductions and computational lower bounds
• On the complexity of k-SAT
• On the complexity of some geometric problems in unbounded dimension
• On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• Parametrized complexity theory.
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
• Tight lower bounds for certain parameterized NP-hard problems

Cited in

(11)

• Fixed-parameter complexity and approximability of norm maximization
• The parameterized complexity of stabbing rectangles
• The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• Interval Stabbing Problems in Small Integer Ranges
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
• Stabbing rectangles by line segments -- how decomposition reduces the shallow-cell complexity
• Integer programming approaches for minimum stabbing problems
• Approximation algorithms for orthogonal line centers
• Algorithms for high dimensional stabbing problems

This page was built for publication: Fixed-parameter tractability and lower bounds for stabbing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q359746)