\(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point

DOI10.1016/j.ipl.2018.09.002zbMath1478.68423OpenAlexW2891878174MaRDI QIDQ1621499

Apurva Mudgal, Raghunath Reddy Madireddy

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

zbMATH Keywords

computational geometryNP-hardnessgeometric hitting setgeometric set coveraxis-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)

Related Items (3)

An approximation algorithm for submodular hitting set problem with linear penalties ⋮ Weighted geometric set cover with rectangles of bounded integer side lengths ⋮ On the geometric red-blue set cover problem

Cites Work

• Exact algorithms and APX-hardness results for geometric packing and covering problems
• The within-strip discrete unit disk cover problem
• Optimal packing and covering in the plane are NP-complete
• Geometric red-blue set cover for unit squares and related problems
• PTAS for Weighted Set Cover on Unit Squares
• The Rectilinear Steiner Tree Problem is $NP$-Complete

This page was built for publication: \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point