Chvatal's Art Gallery Theorem

Chvatal's Art Gallery theorem came in response to Victor Klee's Art Gallery question. Klee posed his question to Václav Chvátal, then a young mathematician at University of Montreal, in August, 1973. An account of Chvátal's solution - conceptually simple, but entailing a few special cases - appears in [Honsberger, pp. 104-110]. A later, almost trivial proof, has been discovered by Steve Fisk, Bowdoin College. He learned of Klee's question from Chvátal's article, but found the proof unappealing. He continued thinking about the problem and came up with a solution while dozing off on a bus travelling somewhere in Afghanistan. [Berger, pp. 219-228, or Aigner, pp. 165-168, and in greater detail O'Rourke, pp. 3-]. I shall outline that proof below.

The problem is this:

It is clear that if the polygon is convex, its whole interior can be viewed from any one vertex. In general, this is of course not true. So the question is not about a particular polygon, but about the entire family of simple polygons: what is the worst case scenario? What is the minimum number of vertices that would answer the question for every admissible n-gon? [n/3] is the answer to the latter question! It is very easy to construct and example (think of a comb with n triangular teeth) where the required number of vertices is exactly [n/3].

The applet below lets you experiment with various polygonal curves. It could be in two modes: you can either draw diagonals of the polygon or move its vertices around. The idea is to create a polygon triangulation by drawing its diagonals. When finished, i.e., after the maximum possible number of the (non intersecting) diagonals have been drawn, the applet will display one of the possible groups of corners from which the whole interior of the polygon is observable.

The proof proceeds in a few steps:

1. Triangulate the polygon with its diagonals.

2. Show that for such a diagonal triangulation of the polygon, its vertices can be colored with three colors, such that all three colors are present in every triangle of the triangulation.

3. Choose the vertices of the polygon assigned the least frequent color.

Starting from the end, assume a diagonal triangulation has been found satisfying 1 and 2. For example, assume there are B blue vertices, R red vertices and G green vertices. Then obviously B + R + G = n. One of the numbers, does not exceed the other two. Without loss of generality we may assume that

B R and B G.

Then

3·B B + R + G = n,

so that B n/3, and, since B is a whole number,

B [n/3].

Now, still going backwards, given a diagonal triangulation, how do we color the vertices to satisfy #2? Observe that, in a diagonal triangulation, the sides of any triangle are either sides or the diagonals of the polygon, and at most 2 may be of the latter kind. The triangles could only abut each other at the diagonals, not the sides of the polygon. Furthermore, only two triangles in a triangulation may share the same diagonal. It follows that each triangle in a triangulation is adjacent two 1 or 2 other triangles. The neighboring triangles share a side and, consequently, two vertices.

Start with any triangle of the triangulation and color its vertices with three colors in a random fashion. Its neighbor triangles already have two vertices assigned two different colors; the requirements of #2 force a unique color on the remaining vertex. Continue in this manner with 1 or, as the case may be, 2 adjacent triangles until all vertices have been assigned a color. The process stops when on either end we run into a triangle composed of 2 sides and 1 diagonal of the polygon.

1. M. Aigner, G. Ziegler, Proofs from THE BOOK, Springer, 2000
2. E. B. Burger, M. Starbird, The Heart of Mathematics, Key College Publishing, 2000
3. R. Honsberger, Mathematical Gems II, MAA, 1976
4. J. O'Rourke, Computational Geometry in C, Cambridge University Press, 2001

Copyright © 1996-2008 Alexander Bogomolny