We consider special cases of [Figure not available: see fulltext.], [Figure not available: see fulltext.], [Figure not available: see fulltext.], and [Figure not available: see fulltext.] problems for axis-parallel squares and axis-parallel rectangles in the plane, where the objects are intersecting an [Figure not available: see fulltext.], or equivalently a [Figure not available: see fulltext.]. We prove that for axis-parallel unit squares the hitting set and set cover problems are $${\mathsf {NP}}$$NP-complete, whereas the piercing set and independent set problems are in $${\mathsf {P}}$$P. For axis-parallel rectangles, we prove that the piercing set problem is $${\mathsf {NP}}$$NP-complete, which solves an open question from Correa et al. [Discrete & Computational Geometry 2015 [3]]. Further, we give a $${n^{O{\lceil }\log c{\rceil }+1}}$$nOi¾?logci¾?+1 time exact algorithm for the independent set problem with axis-parallel squares, where n is the number of squares and side lengths of the squares vary from 1 to c. We also prove that when the given objects are unit-height rectangles, both the hitting set and set cover problems are $${\mathsf {NP}}$$NP-complete. For the same set of objects, we prove that the independent set problem can be solved in polynomial time.
['Apurva Mudgal', 'Supantha Pandit']
Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line