# Art Gallery Theorem

(Difference between revisions)
 Revision as of 19:03, 21 July 2013 (edit)m ← Previous diff Revision as of 19:22, 21 July 2013 (edit) (undo)Next diff → Line 38: Line 38: [[Image: Concave.jpg|300px|center]] [[Image: Concave.jpg|300px|center]] - We need to take into account the fact that guards are limited by the amount of edges they cover because reflex angles greater than $180\, ^{\circ}$ can block a guard's view of consecutive edges. + We need to take into account the fact that guards are limited by the amount of edges they cover because reflex angles greater than $180\, ^{\circ}$ blocks 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. 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. Line 307: Line 307: |Field=Graph Theory |Field=Graph Theory |InProgress=Yes |InProgress=Yes + } + |Field=Algebra + |InProgress=No }} }}

## Revision as of 19:22, 21 July 2013

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.

# 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 $360\, ^{\circ}$ 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 $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$

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, $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. By polygon, we mean a closed collection of $n$ vertices $\left \{ {v_1, v_2, ..., v_n} \right\}$ forming edges $[ \overline{v_1v_2}, \overline{v_2v_3}, ..., \overline{v_{n-1}v_n}, \overline{v_nv_1}]$ 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 $180\, ^{\circ}$. 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 $180\, ^{\circ}$.

We need to take into account the fact that guards are limited by the amount of edges they cover because reflex angles greater than $180\, ^{\circ}$ blocks 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. 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, $q$ and $j$, which form a line segment. For this line segment, $\overline{qj}$, we note that all its interior points 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. 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 $\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 $P$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 $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 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 $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 to $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 to account for the fact that the side count for the two smaller polygons both included the diagonal.

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, $P$. More specifically, three consecutive vertices $\left \{ {a, b, c} \right\}$ of constituent $\bigtriangleup abc$ will form an ear at $b$, provided that one of its edge, $\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.

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

Proof: For a graph $G$ with a finite set of vertices and edges, there exists a walk such that each pair of consecutive vertices defines an edge. The graph is said to be connected if there exists a walk between every pair of vertices. Sometimes walks can form cycles, if they are closed and its first vertex and its last vertex 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 $m$edges 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 triangulation. Then, vertices are connected by an edge to indicate that they are within triangulations that share a non-crossing diagonal of the original polygon, $P$ between them.

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 vertices by $m=n-1$, with 21 edges too. 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$.

## 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

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$ represents 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 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 $P$. Thus, the yellow guards cover the entire polygon and there is at most $\lfloor n/3 \rfloor$ 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,

# 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