NP-hardness of geometric set cover and hitting set with rectangles containing a common point

DOI10.1016/J.IPL.2018.09.002MaRDI QIDQ1621499zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

axis-parallel rectanglescomputational geometrygeometric hitting setgeometric set coverNP-hardness

Mathematics Subject Classification ID

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

Recommendations

• Approximability and hardness of geometric hitting set with axis-parallel rectangles
• On the hardness of some geometric optimization problems with rectangles
• Covering, hitting, piercing and packing rectangles intersecting an inclined line
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions

Cites work

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

Cited in

(11)

• Approximability and hardness of geometric hitting set with axis-parallel rectangles
• Weighted geometric set cover with rectangles of bounded integer side lengths
• On the hardness of some geometric optimization problems with rectangles
• On the geometric red-blue set cover problem
• scientific article; zbMATH DE number 1670858 (Why is no real title available?)
• Geometric hitting set, set cover and generalized class cover problems with half-strips in opposite directions
• Covering, hitting, piercing and packing rectangles intersecting an inclined line
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Geometric Set Cover and Hitting Sets for Polytopes in R
• Discriminating code and set cover with k-bend paths
• An approximation algorithm for submodular hitting set problem with linear penalties

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1621499)