Art galleries with k-guarded guards

Abstract

The k-guarde art galllery problem asks for the minimum number of k-guarded point guards that can collectively monitor a simple polygon with n vertices. A guard is k-guarded if it can see k other guards. For k = 0, this problem is equivalent to the classical art gallery problem of Klee. For k 0 1, a tight bound of $\bigl \lfloor {{3n-1} \over 7} \bigl\rfloor$ was shown recently by Micheal and Pinviu and independently, by Zilinski. In this paper, we settle the problem for every $k ≥ 2$ and show that $k {\bigl\lfloor {n \over 5} \bigl\rfloor} + \bigl\lfloor {{n+2} \over 5} \bigl\rfloor$ k-guarded guards are always sufficient and sometimes necessary to guard a simple polygon with n vertices.