Watchman routes for lines and line segments ?
Given a set L L of non-parallel lines in the plane, a watchman route (tour) for L L is a closed curve contained in the union of the lines in L L such that every line is visited (intersected) by the route; we similarly define a watchman route (tour) for a connected set S S of line segments. The watchman route problem for a given set of lines or line segments is to find a shortest watchman route for the input set, and these problems are natural special cases of the watchman route problem in a polygon with holes (a polygonal domain). In this paper, we show that the problem of computing a shortest watchman route for a set of n  non-parallel lines in the plane is polynomially tractable, while it becomes NP-hard in 3D. We give an alternative NP-hardness proof of this problem for line segments in the plane and obtain a polynomial-time approximation algorithm with ratio O ( log 3 n ) . Additionally, we consider some special cases of the watchman route problem on line segments, for which we provide exact algorithms or improved approximations.
watchman route np-hardness dynamic programming