k-Transmitter Watchman Routes
share
We consider the watchman route problem for a k-transmitter watchman: standing at point p in a polygon P, the watchman can see q∈ P if pq intersects P's boundary at most k times – q is k-visible to p. Traveling along the k-transmitter watchman route, either all points in P or a discrete set of points S⊂ P must be k-visible to the watchman. We aim for minimizing the length of the k-transmitter watchman route. We show that even in simple polygons the shortest k-transmitter watchman route problem for a discrete set of points S⊂ P is NP-complete and cannot be approximated to within a logarithmic factor (unless P=NP), both with and without a given starting point. Moreover, we present a polylogarithmic approximation for the k-transmitter watchman route problem for a given starting point and S⊂ P with approximation ratio O(log^2(|S|· n) loglog (|S|· n) log(|S|+1)) (with |P|=n).
READ FULL TEXT