Fixed-parameter tractability and lower bounds for stabbing problems
type: Item
instance of: scholarly article
title: Fixed-parameter tractability and lower bounds for stabbing problems
zbMATH Open document ID: 1292.65019
author: Panos Giannopoulos
author: Christian Knauer
author: Günter Rote
author: Daniel Werner
published in: Computational Geometry
publication date: 2013-08-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/0906.3896
full work available at URL: S0925772111000502
reviewed by: Juan Monterde
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 6200816
zbMATH Keywords: geometric stabbing
zbMATH Keywords: minimum enclosing cylinder
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: complexity
zbMATH Keywords: algorithm
MaRDI profile type: Publication
OpenAlex ID: W2152358132
arXiv ID: 0906.3896
cites work: Approximate clustering via core-sets
cites work: On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching
cites work: Geometric clustering
cites work: Q3579411
cites work: SEPARATING POINTS BY AXIS-PARALLEL LINES
cites work: A (slightly) faster algorithm for klee's measure problem
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: Linear FPT reductions and computational lower bounds
cites work: Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
cites work: The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
cites work: Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
cites work: Parametrized complexity theory.
cites work: Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
cites work: Approximation algorithms for hitting objects with straight lines
cites work: Fixed-Parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing
cites work: On the complexity of \(k\)-SAT
cites work: Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
cites work: Covering things with things
cites work: Algorithms – ESA 2005
cites work: On the complexity of some geometric problems in unbounded dimension
cites work: Approximating the Radii of Point Sets
cites work: Constant approximation algorithms for rectangle stabbing and related problems
DOI: 10.1016/J.COMGEO.2011.06.005
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 si…
description: scientific article; zbMATH DE number 6200816