2026-08-25T15:33:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27160 2026-08-25T13:18:16Z ddc:004 open_access

On the See-Through Watchman Route Problem and the Quota-TSP Problem on Infinite Lines Mitchell, Joseph S. B. Nguyen, Linh Watchman route problem TSP with neighborhoods The classic Watchman Route Problem (WRP) seeks to compute a shortest tour in a polygonal domain that sees every point of the domain. We introduce and study a novel generalization of the WRP, the See-Through Watchman Route Problem (STWRP), in which, in addition to vision-blocking "walls" of an input domain, there are obstacles to motion that are not opaque to vision: the watchman can see through certain obstacles or portions of the boundary of a polygonal domain P. This setting is motivated by real-world situations that may include transparent barriers (e.g., glass walls), obstacles that obstruct movement but not vision (e.g., lakes, flowerbeds, or potholes), and robotic sensors with penetration capabilities (e.g., microwave imaging). To the best of our knowledge, this version of the problem is new to the algorithms community. Our main result is an FPTAS for the STWRP in the case that P is an opaque-walled simple polygon having within it a set of transparent obstacles. A closely related problem that arises in this setting is that of the Traveling Salesperson problem with neighborhoods (TSPN) on a set of lines in the plane, with obstacles. We give the first FPTAS for the Quota-TSPN on infinite lines with polygonal obstacles. Additionally, we show tightness of our FPTAS, in that the Quota-TSPN on infinite lines with obstacles is weakly NP-hard. In the case of the STWRP within a simple polygon P with portions of the boundary, ∂ P, being transparent, we prove that the problem is NP-hard to approximate within a factor better than O(log n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joseph S. B. Mitchell and Linh Nguyen 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.24 urn:nbn:de:0030-drops-271605 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.24 eng https://creativecommons.org/licenses/by/4.0/legalcode