2026-09-05T07:04:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26047 2026-06-23T13:18:35Z ddc:004 open_access

Improved Approximation of Two Watchmen’s Routes in Simple Polygons Brötzner, Anna Nilsson, Bengt J. Schmidt, Christiane Art gallery problem watchman route problem multiple watchmen path planning 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Brötzner and Bengt J. Nilsson and Christiane Schmidt 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.11 urn:nbn:de:0030-drops-260472 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.11 eng https://creativecommons.org/licenses/by/4.0/legalcode