2024/12/19 by Biniaz, Ahmad, Maheshwari, Anil, Mitchell, Joseph S. B. +3 · 1 citation
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2412.15053
We study the problem of guarding the boundary of a simple polygon with a minimum number of guards such that each guard covers a contiguous portion of the boundary. First, we present a simple greedy algorithm for this problem that returns a guard set of size at most OPT + 1, where OPT is the number of guards in an optimal solution. Then, we present a polynomial-time exact algorithm. While the algorithm is not complicated, its correctness proof is rather involved. This result is interesting in the sense that guarding problems are typically NP-hard and, in particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguous boundary guarding constraint. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most \lfloor (n-2)/(2)\rfloor guards. This bound is tight because there are polygons that require this many guards.