Covering, Hitting, Piercing and Packing Rectangles Intersecting an Inclined Line

We consider special cases of

,

,

, and

problems for axis-parallel squares and axis-parallel rectangles in the plane, where the objects are intersecting an

, or equivalently a

. We prove that for axis-parallel unit squares the hitting set and set cover problems are \({\mathsf {NP}}\)-complete, whereas the piercing set and independent set problems are in \({\mathsf {P}}\). For axis-parallel rectangles, we prove that the piercing set problem is \({\mathsf {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)}}\) 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}}\)-complete. For the same set of objects, we prove that the independent set problem can be solved in polynomial time.