A PTAS for the horizontal rectangle stabbing problem

Arindam Khan, Aditya Subramanian, Andreas Wiese

We study rectangle stabbing problems in which we are given $n$ axis-aligned rectangles in the plane that we want to stab, i.e., we want to select line segments such that for each g…