Art Gallery Theorem

From Math Images

Jump to: navigation, search


Libeskind Building, Berlin Jewish Museum

The zig-zag structure of the Berlin Jewish Museum, known as the Libeskind Building, is one example of the many wacky shaped art museums located around the world. The museum's polygonal shape lends itself to an interesting problem of guard security.


Contents

Basic Description

Imagine you are the director of an art gallery, where security measures must be taken in order to ensure the protection of valuable artworks. Guards are available, but you need to save costs and hire the fewest number of guards as possible. In other words, what is the minimum number of guards needed?

To answer this question, it is clear that the number of guards needed depend on the gallery's shape.

The secure placement of these three guards rests upon the condition that all points of the gallery are visible to at least one guard. It is assumed that the guards will stay in one place, but will be able to view the surrounding gallery area within a 360˚ range from that location. If placed in a gallery corner, a guard can see along adjacent walls.

Figure 1Three examples of the area one guard (denoted by the red dot) can cover." The area's boundaries are called the sight lines. All guards can only watch over so much, for their line of sight does not permit them to see through walls or around corners.
Figure 1
Three examples of the area one guard (denoted by the red dot) can cover." The area's boundaries are called the sight lines. All guards can only watch over so much, for their line of sight does not permit them to see through walls or around corners.


An Art Gallery Problem

We present the following art gallery problem:

For all polygonal-shaped art galleries with n sides such that n\geq 3, what is the minimum number of guards, g(n), sufficient to protect it?

A More Mathematical Explanation

Note: understanding of this explanation requires: *Graph Theory

Chvátal's Art Gallery Theorem

We present a generalized solution to the preceding question, forma [...]

Chvátal's Art Gallery Theorem

We present a generalized solution to the preceding question, formally known as Chvátal's Art Gallery Theorem:

Let n be an integer with n\geq 3. Then the upper bound for the minimum number of guards needed to cover a polygon with n sides is \lfloor n/3 \rfloor. In other words, the sufficient number of guards is:

g(n)= \lfloor n/3 \rfloor

We will now delve into the specifics of this theorem. A basic knowledge of Field:Graph Theory is useful to understanding the concepts leading up to a proof of Chvátal's Art Gallery Theorem, known as Fisk's Short Proof. We will be using the Libeskind Building as the model polygon, P, to illustrate concepts such as triangulation, three-coloring and ears before such a formal proof can be undertaken.

Definition of a Polygon

Chvátal's Art Gallery Theorem refers to a polygonal shaped art gallery. When we refer to such a polygon, we mean a simple polygon whose edges and interior represent the gallery's walls and interior, respectively.


A triangle is an example of a polygon. Moreover, it is a convex polygon because all its interior angles are less than 180˚. As such, all points inside the polygon are visible to each other. The solution to the art gallery problem is easy if there is only a convex polygon involved; there will always be a minimum of 1 guard needed.

Figure 2a
Figure 2a


However, the art gallery problem becomes more complex when we are dealing with concave polygons that have at least one interior angle greater than 180˚.

Figure 2b
Figure 2b


We need to take into account the fact that guards are limited by the amount of edges they cover because reflex angles block a guard's view of consecutive edges. It is hard to find an exact minimum of guards for a concave polygon, as its shape becomes more complex and varied as the number of sides increase. This leads us to the problem of sufficiency. In the crown-shaped polygon down below, there must be a guarantee that 8 guards will be present for protection or else the polygon will not be covered.

Sufficiency acts as a 'catch-all' for various convex polygons of n sides. Although a total up to 8 guards can guard the 24-sided Libeskind polygon, less guards are sufficient as later sections will show.

Figure 3
Figure 3


Triangulations of Polygons

A key part to Fisk's short proof of the art gallery theorem is that polygons can be divided into constituent triangles via diagonals. This process is known as triangulation.

In the figure below, we draw a line segment between two non-consecutive vertices, q and j. Note that all the interior points of \overline{qj} are also within the interior of a polygon. As such, line segment \overline{qj} is a diagonal of the polygon.

Furthermore, two diagonals of a polygon that only intersect at an endpoint are said to be noncrossing. A polygon can be decomposed into smaller polygons by noncrossing diagonals.

Figure 4a  Non-crossing diagonals  and  intersect at common endpoint j, forming the smaller polygon .
Figure 4a
Non-crossing diagonals \overline{qj} and \overline{pj} intersect at common endpoint j, forming the smaller polygon qjp.


However, we will need to be more detailed with our definition of a decomposition. A set of non-crossing diagonals, S, will split a polygon into smaller polygons, denoted by set P \left \{ {P_1, P_2, ..., P_t} \right\}. These smaller polygons will share its vertices with the original polygon. If each smaller polygon in set Pshares exactly three of those original vertices, then the decomposition is a triangulation.

Figure 4b An example of a triangulation of the Libeskind building. The set :  creates the set : of smaller triangles.
Figure 4b
An example of a triangulation of the Libeskind building. The set S: [\overline{ac}, \overline{xc}, \overline{xd}, \overline{wd}, \overline{we}, \overline{ev}, \overline{vf}, \overline{fu}, \overline{ug}, \overline{gt}, \overline{gs}, \overline{hs}, \overline{si}, \overline{ir}, \overline{jr}, \overline{jg}, \overline{jp}, \overline{kp}, \overline{lp}, \overline{lo}, \overline{om}] creates the set P:\left \{ {P_1, P_2, ..., P_{22}} \right\} of smaller triangles.


Looking at Figure 4b above, we see that the 24-sided polygon contains 22 smaller triangles created by 21 non-crossing diagonals. This leads us to the following:


Proposition: Every triangulation of a n sided polygon uses n-3 diagonals and contains n-2 triangles.

 

Proof: We use induction on the n sides of a polygon P. Consider the basis case, n=3, a polygon which is already a triangle. As such, it is triangulated with no diagonals. Mathematically, this is confirmed by: 3-3=0 diagonals and 3-2=1 triangle.

Assume that the proposition holds for a polygon P with fewer than n sides. Now, consider n greater than 3 for the inductive step. Because a polygon with at least 4 sides has a diagonal, we can insert a diagonal into P for the inductive step. The diagonal breaks polygon P into two smaller polygons, P_1 and P_2 with j and k sides, respectively.

The j and k sides of the smaller polygons can be combined together and rewritten in terms of the original ‘’n’’ sides of the polygon, P as,

Eq. 1        j+k=n+2

where the total number of sides, j and k, including the diagonal is equivalent to the original sides of the polygon P plus the diagonal. The diagonal is counted twice because it is included in the side count for both smaller polygons.

Regarding triangles, we know that by the inductive hypothesis that for P_1 and P_2, there are j-2 and k-2 triangles, respectively. Putting the two smaller triangulations together: 
(j-2) + (k-2)
=j+k-4

By Eq. 1, substitute j+k for n+2. We get that the whole triangulation of P has n+2-4=n-2 triangles.

Regarding diagonals, we know that by the inductive hypothesis that for P_1 and P_2, there are j-3 and k-3 diagonals, respectively. We include the +1 diagonal that was used to split P into P_1 and P_2. Putting the two smaller triangulations together:

(j-3)+(k-3)+1
=j+k-5

By Eq. 1, substitute j+k for n+2 and we get that the whole triangulation of P has n+2-5=n-3 diagonals.

Having proved the basis case and inductive step, this proof by induction is complete.


Ears of Polygons

Now, with the Triangulation theorem verified, we move onto the concept of ears. An ear of a polygon is a constituent triangle with two of its edges making up the exterior of the original polygon. For polygon P below in Figure 5, three consecutive vertices \left \{ {a, b, c} \right\} of constituent \bigtriangleup abc will form an ear at b, provided that one of its edges, \overline{ac}, is an interior diagonal of the original polygon. Constituent triangles made up of different consecutive sets of vertices, \left \{{a, b, c} \right\} and \left \{{m, n, o} \right\}, become non-overlapping ears if they have disjoint interiors.

Figure 5
Figure 5


Meister's Two Ears Theorem: Every polygon with n > 3 vertices has at least two non-overlapping ears.

 

Proof: For a connected graph G with a finite set of vertices and edges, there exists a walk . Sometimes walks can form cycles, if they are closed and its first and last vertices are the same.


From these definitions, we can define a tree as a connected graph containing no cycles. For a tree, we note that a relationship exists between its medges and n vertices such that: 
m=n-1
Within this tree, we should also keep in mind that there are leaves, or vertices that are only adjacent to one other vertex in the graph. Every tree with at least two vertices has at least two leaves.

Now assuming that triangulations exist for all polygons, as proved in Section 2.3, we can create dual tree graphs (D_g) for them. First, we place a vertex within the interior of each triangle within the triangulation of polygon P. Then, those vertices are connected by edges to other vertices that share a non-crossing diagonal within P.

The resulting graph is a tree by the conditions delineated above. Since the dual tree graph has at least 2 vertices for all polygons with more than 3 sides, then it has at least 2 leaves. Let us consider this possibility in the figure below, the 24-sided Libeskind polygon. Its dual tree graph D_g has 22 triangles, each with a vertex, and 21 edges (m=n-1). Now, let’s consider the possibility that the Libeskind polygon has at least 2 leaves. In fact, D_g of P has two leaves, which are the initial and end vertices. The first and last vertices have to be leaves because by definition of a tree, they are not equal and cannot connect to each other in a cycle. Also because of where they are positioned within the walk, they can only connect to one consecutive vertex. So, at least these two vertices must be leaves within a dual tree graph.

We allow the two leaves to represent ears. By what has been established about leaves, they are only found within triangles with disjoint interiors. Those triangles become the non-overlapping ears of the original polygon, P.

Figure 6
Figure 6


Colorings of triangulated polygons

Since we know that every polygon has a triangulation and that Meister's Two Ears Theorem holds, we can begin to construct a 3-coloring of a triangulated polygon.

Figure 7
Figure 7


Within a triangulation, a 3-coloring is obtained by assigning colors to vertices such that adjacent vertices do not share the same color. The three colors repeat themselves throughout the rest of the triangulations. Note that once two different colors are chosen for any two adjacent vertices, the vertices from the rest of the triangulations are forced into a certain pattern of coloring.

3-coloring is particularly illuminative of how guards can sufficiently cover an art gallery. If we let the vertices represent guards, then a set of distinctly colored vertices form a valid set of guards that can sufficiently guard the gallery. In the 3-coloring of the Liebskind polygon above, we see that the set of 8 pink colored vertices form a valid placement of 8 guards sufficient for protection. Alternatively, both the sets of 8 yellow and 8 green colored vertices form valid placements of 8 guards sufficient for protection.

Theorem: Every triangulation graph of a polygon is 3-colorable

 

Proof: We use induction on the n\geq 3 vertices of a triangulated polygon.

For the basis case, n=3 vertices, so this triangulated polygon is a single triangle with 3 vertices; its corresponding graph must be 3-colorable.

Now, for the inductive step involving the following case, n\geq 4, we can assume that any corresponding triangulation, T, for n < 4 vertices is 3-colorable.

By Meister's theorem, the triangulated polygon must contain a triangulation \bigtriangleup {abc} that is an ear. Remove vertex b and consecutive edges \overline{ab} and \overline {bc}. What remains of the ear is \overline {ac}, which becomes the edge of polygon P' with n-1 vertices. Essentially, this polygon P' will have triangulation T' of original polygon P, without \bigtriangleup {abc}.

Then by the premises of induction, T' of P' is 3 colored. From P(n-1) of P', we can proceed to the P(n) case of original P and obtain a 3-coloring for its triangulation. In fact, it is obtained by assigning vertex b a third color distinct from the ones already assigned to vertices a and c in the triangulation, T', of P'. Therefore, the original triangulation, T, is also 3-colored.

Fisk's Short Proof

In response to Chvátal's Art Gallery Theorem, refer to Section 1.1

Suppose that there is a polygon with n sides and vertex set V. From Section 2.3, we know that this polygon has a triangulation T. And from Section 2.5, we also know that the polygon's triangulation is 3-colored with distinct color subsets of {V_1}, {V_2}, {V_3}. Now we use A, B, C to denote the number of times each color from the respective subsets is used in the 3-coloring. If we let N represent the total number of vertices, then A+ B + C= N. For this equality to hold true, each of these quantities cannot be larger than \lfloor N/3 \rfloor. So, for any of the color subsets, V_i\leq \lfloor N/3 \rfloor vertices holds true.

To prove that \lfloor n/3 \rfloor guards is sufficient to cover a polygon with n sides, we consider which color subset has least appeared in the 3-coloring. For the 3-colored triangulation graph down below, it is the subset {V_2} with its yellow-colored vertices e, g, l, k, m, x. We place a guard at each of those yellow-colored vertices. Because each triangle of T includes a vertex of each of the three colors, the guards at the yellow-colored vertices are ensured placement. Furthermore, these yellow colored vertices are inside P because the triangles that they are within share the interior region of the original polygon. Since there is a yellow colored vertex with a guard for each of these triangles, then the set of these vertices sufficiently guard P. Thus, the yellow guards cover the entire polygon and there is at most \lfloor n/3 \rfloor of them.

Figure 8 By the yellow subset of vertices, it is possible that 6 guards are sufficient to guard the Liebskind building.
Figure 8
By the yellow subset of vertices, it is possible that 6 guards are sufficient to guard the Liebskind building.




Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

About the Creator of this Image

Daniel Libeskind is a Polish Jewish architect who designed the Libeskind Building of the Berlin Jewish museum.



References

1. T.S. Michael and V. Pinciu, "Module 07-1, Art Gallery Theorems and Triangulations" at http://dimacs.rutgers.edu/Publications/Modules/Module07-1/dimacs07-1.pdf

2. J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, New York, NY, 1987

3. S. L. Devadoss, J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2012

4.http://www.usna.edu/Users/math/tsm/Research/Book_HowToGuardAnArtGallery_Michael/Sample_Chapter_Art_Gallery_Michael.pdf





If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Personal tools