Fixed-parameter tractability and lower bounds for stabbing problems

DOI10.1016/J.COMGEO.2011.06.005zbMATH Open1292.65019arXiv0906.3896OpenAlexW2152358132MaRDI QIDQ359746FDOQ359746

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

Publication date: 22 August 2013

Published in: Computational Geometry (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/0906.3896

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

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)

Cites Work

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

Cited In (10)

• The parameterized complexity of stabbing rectangles
• Fixed-parameter complexity and approximability of norm maximization
• Geometric hitting set for segments of few orientations
• 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
• Title not available (Why is that?)
• 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)