2022/02/03 by Bengt J. Nilsson, Christiane Schmidt, Nilsson, Bengt J. +1
Computer Science · Business, Management and Accounting · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Facility Location and Emergency Management
paper · pdf · doi:10.48550/arxiv.2202.01757
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(log2(|S|⋅ n) loglog (|S|⋅ n) log(|S|+1)) (with |P|=n).