Figure 2.1 is a polygon with 12 sides. The polygon is not convex, as there is at least one reex angle. The objective of the art gallery problem is to hire the most efficient number of guards required to have vision of each point inside of the polygon. Begin with the process of vertex guards. The most visually optimal way to prove the result
_n
3
_
is by first triangulating the polygon. Every vertex of the polygon can be attached in such a way that the entire polygon is made up of solely triangles. This can be shown in _gure 2.2 below.
Now that the polygon is separated into triangles, we know from the definition of a convex
8
polygon that each triangle created has now become visible by one single guard, and some of them share a common vertex. The vertices …show more content…
With these found common vertices, we can find the minimum number of guards required to have vision on all of the triangles. In this example, the triangles vertices will be separated into three colors: red, blue, and green. Each triangle will have one of each color at its three vertices, a concept first introduced by Fisk [3].
In the figure, there are ten total triangles arbitrarily chosen and triangulated (it doesn’t matter which diagonals used so long as they are interior). Many of the triangles share the same vertices, as now visually evident. There are five blue vertices, four red vertices, and three green vertices. The fewest of that set would be the green vertices, which means the number of guards in this shape that would be required to guard every part of the triangulation is three. In mathematical terms, each vertex can be named a, b, and c. The sum of the vertices will be n, the number of sides in the polygon. It follows that a + b + c = n. One of these sets of vertices will serve as the fewest necessary to maintain vision on all the triangles in the polygon, so it can be arbitrarily named a representing one of the aforementioned sides:
Because a has to be an integer, we say that a _
_n
3
_
is by first triangulating the polygon. Every vertex of the polygon can be attached in such a way that the entire polygon is made up of solely triangles. This can be shown in _gure 2.2 below.
Now that the polygon is separated into triangles, we know from the definition of a convex
8
polygon that each triangle created has now become visible by one single guard, and some of them share a common vertex. The vertices …show more content…
With these found common vertices, we can find the minimum number of guards required to have vision on all of the triangles. In this example, the triangles vertices will be separated into three colors: red, blue, and green. Each triangle will have one of each color at its three vertices, a concept first introduced by Fisk [3].
In the figure, there are ten total triangles arbitrarily chosen and triangulated (it doesn’t matter which diagonals used so long as they are interior). Many of the triangles share the same vertices, as now visually evident. There are five blue vertices, four red vertices, and three green vertices. The fewest of that set would be the green vertices, which means the number of guards in this shape that would be required to guard every part of the triangulation is three. In mathematical terms, each vertex can be named a, b, and c. The sum of the vertices will be n, the number of sides in the polygon. It follows that a + b + c = n. One of these sets of vertices will serve as the fewest necessary to maintain vision on all the triangles in the polygon, so it can be arbitrarily named a representing one of the aforementioned sides:
Because a has to be an integer, we say that a _