Abstract: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_1,W_2$, such that every point $p\in P$ is contained in a segment $\overline{w_1w_2}\subseteq P$ such that $w_1\in W_1$ and $w_2\in W_2$. 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.
From: Christian Rieck [view email]
[v1]
Wed, 24 Jun 2026 13:31:27 UTC (374 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。