\(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
type: Item
instance of: scholarly article
title: \(\mathsf{NP}\)-hardness of geometric set cover and hitting set with rectangles containing a common point
zbMATH Open document ID: 1478.68423
author: Raghunath Reddy Madireddy
author: Apurva Mudgal
published in: Information Processing Letters
publication date: 2018-11-09T00:00:00Z
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 52C15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6975550
zbMATH Keywords: axis-parallel rectangles
zbMATH Keywords: geometric set cover
zbMATH Keywords: geometric hitting set
zbMATH Keywords: NP-hardness
zbMATH Keywords: computational geometry
MaRDI profile type: Publication
full work available at URL: j.ipl.2018.09.002
OpenAlex ID: W2891878174
cites work: Exact algorithms and APX-hardness results for geometric packing and covering problems
cites work: Geometric red-blue set cover for unit squares and related problems
cites work: PTAS for Weighted Set Cover on Unit Squares
cites work: Optimal packing and covering in the plane are NP-complete
cites work: The within-strip discrete unit disk cover problem
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
DOI: 10.1016/J.IPL.2018.09.002
description: scientific article; zbMATH DE number 6975550