The problem
Let $P$ be a simple polygon with $n \ge 3$ vertices: the floor of a gallery. A point $x \in P$ sees a point $y \in P$ if the segment $\overline{xy}$ lies in $P$. A set $G \subseteq P$ guards $P$ if every point of $P$ is seen by some point of $G$, and $g(P)$ is the size of a smallest such set. Victor Klee asked in 1973 for the largest value of $g(P)$ over all simple polygons with $n$ vertices.
For every simple polygon $P$ with $n$ vertices, $g(P) \le \lfloor n/3 \rfloor$. For every $n \ge 3$ there is a simple polygon with $n$ vertices for which $g(P) = \lfloor n/3 \rfloor$.
Proof
Upper bound: $g(P) \le \lfloor n/3 \rfloor$Fisk, 1978
Triangulation. Every simple polygon with $n \ge 4$ vertices has a diagonal, a segment between two vertices whose relative interior lies in the interior of $P$. Let $v$ be the leftmost vertex and $u, w$ its neighbours; $v$ is convex. If $\overline{uw}$ is a diagonal we are done. Otherwise the closed triangle $uvw$ contains another vertex of $P$, and the one farthest from the line $uw$, say $x$, gives the diagonal $\overline{vx}$. Cutting along a diagonal splits $P$ into two simple polygons with fewer vertices, so by induction $P$ has a triangulation $T$: $n - 3$ diagonals dividing $P$ into $n - 2$ triangles.
Three-colouring. There is a colouring $c : V(P) \to \{1, 2, 3\}$ under which the three vertices of every triangle of $T$ receive distinct colours. For $n = 3$ this is clear. For $n \ge 4$, the dual graph of $T$, with one node per triangle and an edge for each shared diagonal, is a tree on $n - 2 \ge 2$ nodes and so has a leaf. A leaf triangle $uvw$ has two sides on the boundary of $P$, say $\overline{uv}$ and $\overline{vw}$. Deleting $v$ leaves a triangulated simple polygon on $n - 1$ vertices; colour it by induction and give $v$ the colour used by neither $u$ nor $w$.
Pigeonhole. Let $C_i = c^{-1}(i)$. Since $|C_1| + |C_2| + |C_3| = n$, some class has $|C_i| \le n/3$, and because $|C_i|$ is an integer,
$$|C_i| \le \left\lfloor \frac{n}{3} \right\rfloor.$$
Every triangle of $T$ has exactly one vertex in $C_i$, and a triangle is convex, so that vertex sees all of it. The triangles cover $P$, so $C_i$ guards $P$. $\blacksquare$
Lower bound: the comb
Let $n = 3k$. The comb is a polygon with $k$ narrow teeth on a common base, shaped so that no point of $P$ sees the tips of two different teeth: the set of points that see a given tip is a thin wedge below that tooth, and the wedges of different teeth are disjoint. Each tip needs its own guard, so $g(P) \ge k = \lfloor n/3 \rfloor$. For $n = 3k + 1$ or $3k + 2$, add one or two vertices along the base, which changes neither the teeth nor $\lfloor n/3 \rfloor$. Together with the upper bound, $g(P) = \lfloor n/3 \rfloor$. $\blacksquare$
Remarks
- Fisk’s guards stand on vertices, so the bound holds even when guards must stand in the corners of the gallery.
- If every wall is horizontal or vertical, $\lfloor n/4 \rfloor$ guards suffice and are sometimes necessary (Kahn, Klawe and Kleitman, 1983).
- Computing $g(P)$ for a given polygon is NP-hard (Lee and Lin, 1986).
References
- V. Chvátal, A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B 18 (1975), 39–41.
- S. Fisk, A short proof of Chvátal’s watchman theorem, J. Combin. Theory Ser. B 24 (1978), 374.
- J. Kahn, M. Klawe and D. Kleitman, Traditional galleries require fewer watchmen, SIAM J. Algebraic Discrete Methods 4 (1983), 194–206.
- D. T. Lee and A. K. Lin, Computational complexity of art gallery problems, IEEE Trans. Inform. Theory 32 (1986), 276–282.
- J. O’Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.