Improved Approximation of Two Watchmen’s Routes in Simple Polygons

We study the watchman route problem for a set of two watchmen for the objective of minimizing the length of the longest route (min-max) inside a simple polygon P having n vertices, which is known to be weakly NP-hard. First, we consider seeing a discrete set of m points in the interior of P. We show that even this problem is weakly NP-hard and present an approximation algorithm with approximation ratio 2+ε that runs in O(m⁵n) time, assuming that a starting point for each of the two routes is given. We generalize the algorithm to see all of the interior of P in O(n⁶) time with approximation ratio 2 + π/2 ≈ 3.571, improving on the previously known best algorithm that has an approximation ratio of ≈ 6.922 and runtime O(n²) [Bengt J. Nilsson and Eli Packer, 2024]. Finally, we describe how to extend this algorithm to the case where no starting points are given, this taking O(n⁸) time, yielding an approximation ratio of 3 + π/2 ≈ 4.571, improving on the previously known best approximation algorithm with ratio ≈ 5.969 also having runtime O(n⁸) [Bengt J. Nilsson and Eli Packer, 2024].