Approximability and hardness of geometric hitting set with axis-parallel rectangles

DOI10.1016/j.ipl.2018.09.003zbMath1478.68424OpenAlexW2890680374MaRDI QIDQ1621500

Raghunath Reddy Madireddy, Apurva Mudgal

Publication date: 9 November 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.09.003

zbMATH Keywords

computational geometryNP-hardnessAPX-hardnessgeometric hitting setaxis-parallel rectangles

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

Exact algorithms and hardness results for geometric red-blue hitting set problem

Cites Work

• Exact algorithms and APX-hardness results for geometric packing and covering problems
• The within-strip discrete unit disk cover problem
• Improved results on geometric hitting set problems
• Optimal packing and covering in the plane are NP-complete
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Geometric red-blue set cover for unit squares and related problems
• PTAS for Weighted Set Cover on Unit Squares
• Approximation schemes for covering and packing problems in image processing and VLSI
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes

This page was built for publication: Approximability and hardness of geometric hitting set with axis-parallel rectangles