Article ID Journal Published Year Pages File Type
10225739 Information Processing Letters 2019 8 Pages PDF
Abstract
We prove that both set cover and hitting set problems with points and axis-parallel rectangles are NP-hard even when (i) all rectangles share a common point and (ii) there are only two types of rectangles a×b and b×a for some positive integers a and b.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
NP-hardness of geometric set cover and hitting set with rectangles containing a common point
Authors
, ,