Figure 1
Geometric Structures: Session III
Art Galleries, Visibility, and Triangulations
Prepared by:
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk
While there are certainly many new theorems about triangles, quadrilaterals, and circles yet to be discovered, such questions do not currently engage most people doing research in geometry nor are they the kind of geometry questions that seem to be suggested by emerging new technologies.
An example of a very simple environment which has lead to lots of productive new geometrical questions deals with visibility. Here is a question originally raised by the late Victor Klee, one of America's most distinguished geometers.
Suppose one is given the floor plan of an art museum (Figure 1) which is a simple polygon P with n vertices. Guards are to be placed at the vertices of P which serves as a model for museum. A guard at vertex v can see a point w of the interior of the museum or on its boundary, if the line segment from v to w does not contain any points of the exterior of P. One is interested in find locations for placing guards so that any interior point is visible to some guard.
Problem 1: In terms of n, what is the number of guards that is sometimes necessary and always sufficient to guard a museum with n vertices?
What is meant is that if g(n) gives the answer, one can find a plane simple polygon with n sides which needs g(n) guards and that given ANY n-sided polygon, one can guard it with g(n) or fewer guards.
The problem raised above is sometimes confused with the following similar sounding but very different question:
Problem 2: Given a simple polygon P, what is the minimum number of vertex guards to see all the interior points of P?
This optimization problem turns out to be NP-complete. NP-completeness refers to a class of problems which are "equally difficult" in the following sense. If any NP-complete problem could be solved using an algorithm which required a polynomial amount of time, then all NP-complete problems could be solved using a polynomial time algorithm. On the other hand, if it could be shown that any one of these problems required an exponential time algorithm to solve, then they all would require an exponential time algorithm. It is widely believed that NP-complete problems are unlikely to be solvable using polynomial time algorithms.
Problem 1, unlike Problem 2, has been solved in a satisfactory manner. The problem went unresolved for a few years after Klee posed it. Eventually, Vasek Chvatal solved the problem using an elementary but somewhat involved argument. However, a few years after Chvatal's resolution of the problem, Steve Fisk (unfortunately now deceased) gave a very elegant solution.
Fisk's proof is based on the idea of triangulating a simple polygon. Figure 2 shows a way of drawing internal diagonals to the polygon in Figure 1 so that the polygon is decomposed into triangular regions. Note that the edges in the interior of the polygon, the thin edges, join existing vertices of the polygon.
While it seems intuitively clear that this is always possible, it is not a totally easy fact to establish. One observation that may give one pause is whether or not the plane version of the theorem generalizes to 3-space.
Given a not-necessarily convex polyhedron in 3-space (but one which is topologically equivalent to a sphere, homeomorphic to a sphere), can one using the existing vertices of the polygon decompose the polyhedron into tetrahedra? (A pair of geometric figures are homeomorphic if there is a one-to-one onto mapping h between the figures where h and its inverse are both continuous functions.)
The perhaps surprising answer to this question is no! There are polyhedra in 3-space with the property that if two vertices v and w of the polyhedron are not already joined by an edge of the polyhedron, then the edge joining v and w lies totally in the exterior of the polyhedron! Polyhedra of this kind are sometimes called Lennes Polyhedra after the American topologist N. J. Lennes. However, polyhedra of this kind were already described by E. Schonhardt (1928). It turns out that if one allows the addition of points other than the vertices of the polyhedron to the interior of the polyhedron (such points are known as Steiner points after Jacob Steiner), then any non-convex polyhedron homeomorphic to a sphere can be decomposed into tetrahedra. (One can also discuss the idea of Steiner points in discussing decomposing polygons into parts.)
To show that any simple polygon can be triangulated it suffices to use a nifty idea of Gary Meisters. The "trick" is to look for "ears" of a simple polygon P. A vertex v of a simple polygon is an ear if uv and wv are the two edges of the polygon that meet at v then the segment uw lies totally in the interior of P.
The vertex v in Figure 3 is an ear as shown by the fact that the very thick edge uw is totally interior to the polygon.
In Figure 3 all of the vertices which have interior angles of less than 180 degrees are ears.
Do now 1:
Draw a family of simple polygons P(n) (n at least 4) where the polygon P(n) has only exactly 2 ears.
Ear Theorem (Gary Meisters)
Any simple polygon has at least two ears.
Using the Ear Theorem one can start with a simple polygon and locate an ear. This ear can be "removed," resulting in a polygon with one few vertex. Now one can find an ear of this polygon which has fewer vertices. Using the diagonals that define the ears in this process one can triangulate the original polygon.
Now, Fisk observed that if one has a triangulated simple polygon (the original polygon together with internal diagonals joining existing vertices) and one labels (colors) the vertices of one triangle in this triangulation so that two vertices jointed by an edge get different colors, then one can uniquely continue this coloring (labeling) of the vertices of the triangulation so that every vertex gets a color and so that vertices joined by an edge get different colors using exactly 3 colors. (Note: not all plane graphs can have their vertices colored with 3 colors; the famous 4-color theorem says that the vertices of any planar graph can be 4-colored so no two vertices joined by an edge get the same color.)
For our original art gallery (Figure 1), Figure 4 shows how to color the vertices of a triangulated version of this polygon with 3 colors.
The three colors or labels used to color the triangulated polygon's vertices are a, b, and c. Note that a is used 3 times, b is used 3 times and c is used twice. Also, the guard at each vertex of a triangle can see all of the interior points of that triangle. This means that the guards at vertices labeled c can see all the points in the triangles that meet at c. Since every triangle has c as a label, it follows that the guards at vertices labeled c can see all the interior points. However, if there are n vertices, the worst that can happen is that the colors a, b, and c be as equally distributed as possible at the vertices. Thus, the number of guards must always be less than the floor function of n/3. (Floor (x) where x is a real number is the largest integer less than or equal to x. Hence, floor(7/3) = 2 and floor(12/3) = 4.) The conjecture that for an art gallery with n vertices floor(n/3) guards are sometimes necessary and always sufficient to guard any art gallery was already made by Victor Klee. The proof that this result was true, as mentioned above, was shown by Chvatal and Fisk using very different methods.
Notice that if one has a convex 6-gon P, one can find a triangulation of P and a 3-coloring of that triangulation's vertices which shows that one can see all of P with two vertex guards. However, P has another triangulation which leads to a 3-coloring of the vertices of the triangulation which shows that only one guard suffices to see all of P.
Do Now 1:
a. What is the minimum number of vertex guards that are needed for Figure 1?
b. Give an example of an infinite family of polygons which need only one guard as n grows.
c. Some polygons look much more complex than others. Can you define some "measure" of how complex a polygon is?
The work of Klee, Chvatal, and Fisk unleashed a flood of research about visibility problems for polygons and lead to many different ways to extend the initial problem that Klee posed.
Here are some examples of ways that the initial art gallery problem was extended:
1. Does one need fewer guards when one has museums that have special properties? For example, suppose the only interior angles of the polygon (museum) are 90, 180, or 270 degrees (Figure 5 and Figure 6). How many vertex guards are sometimes necessary and always sufficient for a n-sided polygon?
Figure 5 shows an 18-gon.
Figure 6 shows a 19-gon. A minimum number of guards for Figure 5 will also be able to guard the museum in Figure 6. Polygons such as those in Figure 5 and Figure 6 are called rectilinear polygons or orthogonal polygons. Fisk's approach to proving the Klee-Chvatal result was based on being able to decompose any plane simple polygon into triangles using existing vertices. Can one decompose orthogonal polygons into convex quadrilateral parts? What other ways are there to decompose simple polygons into "nice" parts?
This problem was formulated so that guards were to be placed at vertices. What changes if any occur when the guards can be placed in the interior of the polygon or can be placed at locations on the boundary edges of the polygon other than at vertices? What happens if there are "holes" in the interior of the polygon? Figure 7 shows a rectilinear polygon with holes but where the holes are not rectilinear.
It is still easy to state relatively simple problems for which a solution may yet not have been found. Here is one such circle of ideas. Call a plane simple polygon equilateral if all of its sides have the same length. While regular polygons are equilateral, there are many equilateral polygons which are not regular. Do the same result hold for equilateral polygons as hold for general polygons or does the fact that a polygon is equilateral mean that one can "typically" get away with fewer guards? One can look at general equilateral polygons or equilateral polygons which have additional properties such as being orthogonal.
Although there is a huge literature on Art Gallery Theorems, Joseph O'Rourke's book Art Gallery Theorems and Algorithms, Oxford Press, 1987 is still a wonderful place to get started. (The book can be downloaded for free from the Web.)