The prison yard problem (Q1340137)

Let \(\Pi\) be a simple polygon with \(n\) vertices. The authors prove that \(\lceil n/2 \rceil\) guards located at some vertices of \(\Pi\) suffice to see both the interior and the exterior of \(\Pi\) (the guards cannot see beyond the sides of \(\Pi)\). This theorem solves a problem posed by D. Wood and J. Malkelvitch, and confirms the value \(\lceil n/2 \rceil\) conjectured by \textit{J. O'Rourke} [`Art gallery theorems and algorithms', Oxford Univ. Press, New York (1987; Zbl 0653.52001)]. It is also shown that \(\lfloor n/2 \rfloor\) guards suffice provided the polygon \(\Pi\) is not convex.