2026-08-21T18:34:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27463 2026-08-21T14:42:41Z ddc:004 open_access

Segment Watchman Routes Brötzner, Anna Filtser, Omrit Nilsson, Bengt J. Rieck, Christian Schmidt, Christiane Watchman routes segment guarding k-hull guarding NP-hardness approximation Motivated by applications for robust guarding, we consider a variant of the multiple-watchmen problem that ensures that every point within a polygon P is seen from more than one direction: we search for two routes W₁,W₂, such that every point p ∈ P is contained in a segment w₁w₂ ⊆ P such that w₁ ∈ W₁ and w₂ ∈ W₂. We call such routes segment watchman routes. We show that finding the two routes that are optimal with respect to the min-max criterion is weakly NP-hard even in simple polygons, and that finding the routes that are optimal with respect to the min-sum criterion is NP-hard in polygons with holes. Moreover, we present sufficient conditions for routes to be segment watchman routes, and provide a polynomial-time 2-approximation under both the min-max criterion and the min-sum criterion, both in simple polygons. Finally, we show how to generalize our results for k watchmen. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Brötzner and Omrit Filtser and Bengt J. Nilsson and Christian Rieck and Christiane Schmidt 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.81 urn:nbn:de:0030-drops-274634 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.81 eng https://creativecommons.org/licenses/by/4.0/legalcode