Fixed-parameter tractability and lower bounds for stabbing problems

DOI10.1016/j.comgeo.2011.06.005zbMath1292.65019arXiv0906.3896OpenAlexW2152358132MaRDI QIDQ359746

Panos Giannopoulos, Günter Rote, Christian Knauer, 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

zbMATH Keywords

complexityalgorithmfixed-parameter tractabilitygeometric stabbingminimum enclosing cylinder

Mathematics Subject Classification ID

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

Related Items (5)

The parameterized complexity of stabbing rectangles ⋮ Approximation algorithms for orthogonal line centers ⋮ Geometric hitting set for segments of few orientations ⋮ Unnamed Item ⋮ Fixed-parameter complexity and approximability of norm maximization

Cites Work

• Unnamed Item
• Constant approximation algorithms for rectangle stabbing and related problems
• Approximation algorithms for hitting objects with straight lines
• Covering things with things
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• 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
• Approximate clustering via core-sets
• 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
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• Approximating the Radii of Point Sets
• Algorithms – ESA 2005
• Approximation Algorithms for Rectangle Stabbing and Interval Stabbing Problems
• On the complexity of \(k\)-SAT

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