Constrained Orthogonal Segment Stabbing
share
Let S and D each be a set of orthogonal line segments in the plane. A line segment s∈ S stabs a line segment s'∈ D if s∩ s'≠∅. It is known that the problem of stabbing the line segments in D with the minimum number of line segments of S is NP-hard. However, no better than O( |S∪ D|)-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∪ D intersects a 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.
READ FULL TEXT