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$.

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 – ESA 2005
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• 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)