TY - GEN
T1 - Watchman routes for lines and segments
AU - Dumitrescu, Adrian
AU - Mitchell, Joseph S.B.
AU - Zyliński, Paweł
PY - 2012
Y1 - 2012
N2 - Given a set of non-parallel lines, a watchman route (tour) for is a closed curve contained in the union of the lines in such that every point on any line is visible (along a line) from at least one point of the route; similarly, we define a watchman route (tour) for a connected set 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 multiply connected polygonal domains. 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. Then, we reprove NP-hardness of this problem for line segments in the plane and provide 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 improved approximation or exact algorithms.
AB - Given a set of non-parallel lines, a watchman route (tour) for is a closed curve contained in the union of the lines in such that every point on any line is visible (along a line) from at least one point of the route; similarly, we define a watchman route (tour) for a connected set 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 multiply connected polygonal domains. 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. Then, we reprove NP-hardness of this problem for line segments in the plane and provide 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 improved approximation or exact algorithms.
UR - https://www.scopus.com/pages/publications/84863090205
U2 - 10.1007/978-3-642-31155-0_4
DO - 10.1007/978-3-642-31155-0_4
M3 - Conference contribution
AN - SCOPUS:84863090205
SN - 9783642311543
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 36
EP - 47
BT - Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings
T2 - 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012
Y2 - 4 July 2012 through 6 July 2012
ER -