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

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

• scientific article; zbMATH DE number 5764822 (Why is no real title available?)
• 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 Rectangle Stabbing and Interval Stabbing Problems
• Approximation algorithms for hitting objects with straight lines
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Constant approximation algorithms for rectangle stabbing and related problems
• 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
• Linear FPT reductions and computational lower bounds
• On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching
• On the complexity of \(k\)-SAT
• On the complexity of some geometric problems in unbounded dimension
• 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 algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing
• The parameterized complexity of stabbing rectangles
• Fixed-parameter complexity and approximability of norm maximization
• The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• Algorithms for high dimensional stabbing problems
• scientific article; zbMATH DE number 7561415 (Why is no real title available?)
• Integer programming approaches for minimum stabbing problems
• Interval Stabbing Problems in Small Integer Ranges
• Approximation algorithms for orthogonal line centers

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)