Constrained Orthogonal Segment Stabbing

Let $S$ and $D$ each be a set of orthogonal line segments in the plane. A line segment $s\in S$ \emph{stabs} a line segment $s^{\mathrm{\prime }}\in D$ if $s\cap s’\neq\emptyset$\mathrm{.}Itisknownthattheproblemofstabbingthelinesegmentsin$D$withtheminimumnumberoflinesegmentsof$S$ is NP-hard. However, no better than $O(\log \mathrm{\mid }S\cup D\mathrm{\mid })$-approximation is known for the problem. In this paper, we introduce a constrained version of this problem in which every horizontal line segment of $S\cup D$ intersects a common vertical line. We study several versions of the problem, depending on which line segments are used for stabbing and which line segments must be stabbed. We obtain several NP-hardness and constant approximation results for these versions. Our finding implies, the problem remains NP-hard even under the extra assumption on input, but small constant approximation algorithms can be designed.