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:
Given a simple n-gon, what is the minimum number of vertices from which it is possible to view every point in the interior of the polygon? (Answer: [n/3].)
(A polygon is simple if it has no self-intersections. More accurately, the sides of such a polygon may only meet in their endpoints, and never more than two at a time.)
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.
As of 2018, Java plugins are not supported by any browsers (find out more). This Wolfram Demonstration, Art Gallery Problem, shows an item of the same or similar topic, but is different from the original Java applet, named 'Chvatal'. The originally given instructions may no longer correspond precisely.
The proof proceeds in a few steps:
Triangulate the polygon with its diagonals.
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.
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 and B ≤ G.
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. 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 all triangles adjacent to the current one ( or ones) 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.
Note that - during that vertex coloring process - this is impossible to arrive at a triangle of a diagonal triangulation in two different ways and thus incidently get stuck with contradicting colors. To see this, associate with a triangulation a graph. For the nodes of the graph choose one interior point (say, centroid) in every triangle. Join the chosen points of two adjacent triangle by an edge. The resulting graph is necessarily a tree because having a loop would imply a presence of an "enternal" vertex, a vertex in the inerior of the polygon. Since the triangulation is done solely by the diagonals all vertices of the triangulation coincide with those of the base polygon.
Finally, the diagonal triangulation is always possible. The proof is by induction. Any diagonal that lies entirely in the interior of a polygon splits the latter into two with fewer sides. Find such a diagonal and then apply this same consideration to both constituent polygons until only triangles remain. A triangle, i.e., a 3-gon, is the only element of its only triangulation. The proof of #1 seems thus to be complete. However, it is based on the premise that any simple polygon has at least one diagonal that lies entirely in the interior of the polygon. Is that so?
To see that the answer is affirmative, first prove that there is an angle of the polygon which is less than 180°. This is so because the sum if the internal angles of an n-gon is 180°(n-2). By the Pigeonhole Principle ("the least number is at most the average"), there bound to be an angle not greater than
Imagine point B slide from its initial position along the edge adjacent to AB. It may be that it will reach the next vertex without obstruction. Or the (moving) segment from A may pass through another vertex. However it happens to be, call the first vertex reached by the moving segment C. Then either AC or BC (or both) will serve our purpose. For then, by construction, there could not possibly be any vertices inside the triangle ABC. Had there been any, they would have been met earlier than C by the rotating segment.)