Art Gallery Theorem
From Math Images
m |
|||
Line 51: | Line 51: | ||
In the figure below, we draw a line between two non-consecutive vertices, <math>q</math> and <math>j</math>, which form a line segment. For this line segment, <math>\overline{qj}</math>, we note that all its interior points are also within the interior of a polygon. As such, line segment <math>\overline{qj}</math> is a '''diagonal''' of the polygon | In the figure below, we draw a line between two non-consecutive vertices, <math>q</math> and <math>j</math>, which form a line segment. For this line segment, <math>\overline{qj}</math>, we note that all its interior points are also within the interior of a polygon. As such, line segment <math>\overline{qj}</math> is a '''diagonal''' of the polygon | ||
- | Furthermore, two diagonals of a polygon that only intersect at an endpoint are said to be '''noncrossing'''. We say that a polygon can be '''decomposed''' into | + | Furthermore, two diagonals of a polygon that only intersect at an endpoint are said to be '''noncrossing'''. We say that a polygon can be '''decomposed''' into smaller polygons by '''noncrossing diagonals'''. All this is illustrated in the figure down below, where '''non-crossing''' diagonals <math>\overline{qj}</math> and <math>\overline{pj}</math> intersect at common endpoint ''j'', forming the smaller polygon <math>qjp</math>. |
[[Image:Diagonals2.jpg|700px|center]] | [[Image:Diagonals2.jpg|700px|center]] | ||
Line 57: | Line 57: | ||
[[Image:Triangulation2.jpg|700px|center]] | [[Image:Triangulation2.jpg|700px|center]] | ||
- | Looking at the triangulated image of the art gallery above, we see that the 24-sided polygon contains 22 | + | Looking at the triangulated image of the art gallery above, we see that the 24-sided polygon contains 22 smaller triangles created by 21 non-crossing diagonals. This leads us the following: |
Revision as of 19:03, 21 July 2013
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. Upon placement, the guards can view the surrounding gallery area within a range from their position. If placed in a gallery corner, a guard can see along adjacent walls.
The following are examples of what it takes for a guard (denoted by the red dot) to cover an area of the art gallery. Highlighted are the plausible viewing regions for a guard. The guard's sight lines bound the area that they watch over. A guard 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 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:
To clarify, by cover we mean that the guards can see all the area inside the polygon.
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. By polygon, we mean a closed collection of vertices forming edges such that no common point is shared between any pair of non-intersecting edges. 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 . As such, all points inside the polygon are visible to each other. Thus, 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 will have an interior angle greater than .
We need to take into account the fact that guards are limited by the amount of edges they cover because reflex angles greater than can 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. In the 24-sided crown shaped polygon down below 8 guards are required to guard it. And 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 between two non-consecutive vertices, and , which form a line segment. For this line segment, , we note that all its interior points 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. We say that a polygon can be decomposed into smaller polygons by noncrossing diagonals. All this is illustrated in the figure down below, where non-crossing diagonals and intersect at common endpoint j, forming the smaller polygon .
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. The next figure down below is an example of a triangulation of the Libeskind building because the set : creates the set : of smaller triangles.
Looking at the triangulated image of the art gallery above, we see that the 24-sided polygon contains 22 smaller triangles created by 21 non-crossing diagonals. This leads us 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, . More specifically, three consecutive vertices of constituent will form an ear at , provided that one of its edge, , 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 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 represents 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 interiority 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 within the larger scope of . Thus, the yellow guards cover the entire polygon and there is at most of them.
As illustrated above in this different triangulated version of its polygonal floor plan, 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
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.