Stabbing Polygonal Chains with Rays is Hard to Approximate
Steven Chaplick, Elad Cohen, Gila Morgenstern · Research Publications (Maastricht University) · 2013
We study a geometric hitting set problem involving unirectional rays and curves in the plane. We show that this problem is hard to approxi-mate within a logarithmic factor even when the curves are convex polygonal x-monotone chains. Addition-ally, it is hard to approximate within a factor of 76 even when the curves are line segments with bounded slopes. Lastly, we demonstrate that the problem is W [2]-complete when the curves are convex polygonal x-monotone chains and is W [1]-hard when the curves are line segments. 1