Art Gallery Theorem
From Math Images
Libeskind Building, Berlin Jewish Museum |
---|
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.
An Art Gallery Problem
We present the following art gallery problem:
- For all polygonal-shaped art galleries with sides such that , what is the minimum number of guards, , sufficient to protect it?
- For all polygonal-shaped art galleries with sides such that , what is the minimum number of guards, , 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 . Then the upper bound for the minimum number of guards needed to cover a polygon with n sides is . In other words, the sufficient number of guards is:
- Let n be an integer with . Then the upper bound for the minimum number of guards needed to cover a polygon with n sides is . In other words, the sufficient number of guards is:
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, , 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.
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˚.
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 sides. Although a total up to 8 guards can guard the 24-sided Libeskind polygon, less guards are sufficient as later sections will show.
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, and . Note that all the interior points of are also within the interior of a polygon. As such, line segment 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.
However, we will need to be more detailed with our definition of a decomposition. A set of non-crossing diagonals, , will split a polygon into smaller polygons, denoted by set . These smaller polygons will share its vertices with the original polygon. If each smaller polygon in set shares exactly three of those original vertices, then the decomposition is a triangulation.
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 sided polygon uses diagonals and contains triangles.
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 below in Figure 5, three consecutive vertices of constituent will form an ear at , provided that one of its edges, , is an interior diagonal of the original polygon. Constituent triangles made up of different consecutive sets of vertices, and , become non-overlapping ears if they have disjoint interiors.
Meister's Two Ears Theorem:
Every polygon with vertices has at least two non-overlapping ears.
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.
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
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 sides and vertex set . From Section 2.3, we know that this polygon has a triangulation . And from Section 2.5, we also know that the polygon's triangulation is 3-colored with distinct color subsets of . Now we use to denote the number of times each color from the respective subsets is used in the 3-coloring. If we let represent the total number of vertices, then . For this equality to hold true, each of these quantities cannot be larger than . So, for any of the color subsets, vertices holds true.
To prove that guards is sufficient to cover a polygon with 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 with its yellow-colored vertices , , , , , . We place a guard at each of those yellow-colored vertices. Because each triangle of 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 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 . Thus, the yellow guards cover the entire polygon and there is at most of them.
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
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.