The “Art gallery theorem” or “museum problem” as it is referred to, was originated from the real world situation. There are x amount of guards guarding the gallery, and the goal is to compute the minimal amount of guards needed to guard the entire art gallery. The art galleries are typically given the shape of a polygon. And “a polygon is generally defined as an ordered sequence of at least three points v1,v2…,vn in the plane, called vertices, and the n line segments v1v2, v2v3, …, vn-1vn, and vnv1, called edges.” As for a “simple polygon” it is essentially the same as a polygon but except for the fact that non consecutive edges do not intersect. A simple polygon is also known as a jordan curve which means that it is divided into three subsets, the interior, the polygon itself, and the exterior. What most mathematicians take as their first step is the decomposition of the polygon. And there are many ways to decompose a polygon as the first step, for example there is, “convex polygons”, “spiral polygons”, and “monotone polygons”. Yet when dealing with a star shaped polygon it is shown that one guard is needed to cover the entire polygon when place in the fixed position.
The art gallery theorem was brought up within a conversation between “Klee” and “Chvatal”. This theorem was proposed to calculate the minimal amount of guards needed to cover any polygon. As Chvatal began to work on the problem he began to realize that g(n)=[n/3] (n= number of walls), and this was the way to find the minimal amount of guards needed. Later on “Fisk” gave a concise proof stating that you needed to triangulate the polygon then assign each vertex one of the three different colors. So this way it prevented any adjacent vertices from having the same color. What has also been stated about the art gallery problem is that based on the placement of the guards which was stated by both Avis and Toussaint. They both believed that there was a set of guards that were needed to cover the polygon yet that there was an algorithm to find the placement of each guard.
When approaching the art gallery theorem most first steps is to make the polygon into a polygon triangulation (if not possible try other decompositions based on the shape). This means that the polygon is broken up into triangles which are generated by the diagonals within the polygon. There are also different ways of guarding the polygon. For example, there is a “covering guard set” and a “hidden set”. The difference between the two is that in a “covering guard set” each guard is able to see one another. As for in the “hidden set” each guard is placed in a spot of the polygon where they are incapable of seeing one another.
When dealing with orthogonal comb polygons Kahn, Klawe, and Kleitman showed that the maximum of guards needed was the way solving such a polygon “orth(n)>[n/4]”. They also took the idea of triangulating the polygon but tweaked it a bit by dividing the polygon into “convex quadrilaterals”. They also used four colors instead of three, and this caused there to be all four colors at each vertex. This is an example of one the polygons in which needed to use a different decomposition instead of just triangulating the polygon.
Given information that has been proven is that when n=5 or less one guard will be needed to cover the polygon. Another given hint is that in some 6-vertex polygons there are only two guards needed when placed in a fixed position.
Works cited:
- Shermer, Thomas C. "Recent Results in Art Galleries." Recent Results in Art Galleries (geometry) - Proceedings of the IEEE (n.d.): n. pag. Sept. 1992. Web. 17 Nov. 2014.
- Avis, David, and Godfried Toussaint. "An Efficient Algorithm for Decomposing a Polygon into Star-shaped Polygons." Pattern Recognition 13.6 (1981): 395-98. 9 Dec. 1999. Web. 17 Nov. 2014.
- O'rourke, Joseph. "ART GALLERY THEOREMS AND ALGORITHMS." (1987): 1-296. Oxford University Press. Web. 17 Nov. 2014.
This is an interesting topic to read about, because of how it can be applied to a real life problem. I was still a little confused when I read through this. For example, I didn't know what it meant to triangulate. I did manage to find this video that help visualize this theorem though: https://www.youtube.com/watch?v=HbDmmWERMME. I wonder if actual buildings try to use this concept because it could also help optimally place cameras within the building too.
ReplyDeleteI thought that this concept was very interesting. It's pretty cool that there's a way to calculate the smallest amount of guards needed to guard a museum in the shape of a polygon. The idea of the "covering guard set" and "hidden set" is very interesting as well and makes me wonder whether this happens in some mathematical based museums.
ReplyDeleteI have never heard about this before! It is very interesting knowing that they design the buildings so that there are a small amount of guards. Your post really explained the concept well but I agree with Zach. Zach, the video you found really helped me visualize this concept!
ReplyDeleteThis topic intrigued me as it applies to a real world situation to determine the minimum amount of guards needed to monitor the gallery. It would be cheaper since you would have a minimum amount which would be less than what you started. The shapes of the galleries and museums determine the exact minimum amount needed to guard the place which I thought was interesting since there is an exact number.
ReplyDeleteI, not having any prior knowledge of the art theorem, can understand it now thanks to the visual examples given to me in the post. This being a different theorem than most we've read about or discussed in class was quite refreshing to the brain. I particular liked the picture showing the angle of the guards and how they cover the museum. Great Summary!
ReplyDeleteThis concepts and the math that accompany it seem beyond me, even after this post. Things start to get really complicated with increasingly sided polygons. really the only question that came to my mind while reading was what made you choose this topic? it seems like such an abstract concept and i was wondering how you stumbled upon it?
ReplyDeleteThis is an interesting topic. I also like that it applies to a real life situation. I liked your topic it's very interesting to know they would use a polygon to minimize the amount of guards needed in the museum. The picture definitely helps with explaining your topic. I'm also wandering where you came up with this topic.
ReplyDeleteI have never heard of this before but it was very interesting! The visuals helped me understand the concept a lot more easily, they helped explain your topic. I, too, liked the angle of the guards and how they cover the museum, very cool!
ReplyDeleteThis concept is way past me to be honest. After reading it I still don't know much about it. It's not because you didn't explain it well, it's just that this topic is really hard to grasp. I still think I learned a few things from this read.
ReplyDeleteReading on how the art gallery theorem can be used in real life scenarios was pretty interesting. I also found it cool how you can narrow down the numbers of where a guard is placed by meeting at a certain point.
ReplyDeleteI think that it's always really cool to see the math behind real world situations. People always think that the math behind these situations to be really simple since all you're talking about is guards in a room so it's really cool to see how complex the situation really is. It's certainly a tough topic to grasp but fascinating to see how the geometry of the room has a direct impact in the number of guards.
ReplyDeleteI like the idea and I like how the process of triangulation can make even the more complex shaped floor plans simple to determine on which vertices the guards would cover a wider view of the interior; the museum can save more on labor, very economical!!
ReplyDeleteI had to read this blog for a second time before I understood it. I thought it was nice to know how much math is behind the world. I thought that you had good examples to support your summary. I thought this was a nice blog to read for me.
ReplyDeleteThe idea behind the "art gallery theorem" is really intriguing. The process of triangulation somewhat reminded me of those puzzles that we would sometimes play in school. I think that the math behind this problem could have been explained a little more, but everything else was explained fairly well.
ReplyDelete