Contiguous Boundary Guarding

作     者：Biniaz, Ahmad Maheshwari, Anil Mitchell, Joseph S.B. Odak, Saeed Polishchuk, Valentin Shermer, Thomas 

作者机构：School of Computer Science University of Windsor Canada School of Computer Science Carleton University Canada Department of Applied Mathematics and Statistics Stony Brook University United States School of Electrical Engineering and Computer Science University of Ottawa Canada Linköping Univeristy Sweden School of Computing Science Simon Fraser University Canada 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：NP hard 

摘      要：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 ⌊n−2/ 2⌋ guards. This bound is tight because there are polygons that require this many guards. © 2024, CC BY.