The prison yard problem (Q1340137)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The prison yard problem |
scientific article |
Statements
The prison yard problem (English)
0 references
1 August 1995
0 references
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.
0 references
guard problems
0 references
polygon
0 references
convex
0 references
triangulation
0 references