# Talk:Art Gallery Theorem

(Difference between revisions)
 Revision as of 16:07, 17 July 2013 (edit)← Previous diff Revision as of 18:34, 21 July 2013 (edit) (undo)Next diff → Line 1: Line 1: + =Response to Checklist= + ==Messages to the Future== + ==References and Footnotes== + ==Good Writing== + ===Context=== + ===Quality of Prose and Page Structuring=== + ===Integration of Images and Text=== + ===Connections to other Mathematical Topics=== + ===Examples, Calculations, Applications, Proofs=== + ===Mathematical Accuracy and Precision of Language=== + === Layout=== + =Art Gallery Theorem= =Art Gallery Theorem= [[User:Christaranta|Chris]] 11:26, 8 July 2013 (EDT) [[User:Christaranta|Chris]] 11:26, 8 July 2013 (EDT)

# Art Gallery Theorem

Chris 11:26, 8 July 2013 (EDT) Tell the reader that you will be using the Libeskind Building as the model polygon for explaining the concepts of the Art Gallery Theorem. Got it. yeeyee --Lpeng1 14:37, 11 July 2013 (EDT)

--Chris 10:14, 11 July 2013 (EDT)For Sections 2.3, 2.4, and 2.5 You don't need to put Proof, Proposition, and Theorem as subheadings.

## Basic Description

Chris 11:26, 8 July 2013 (EDT)

• P1, S2: Change "least number of guards as possible" to "fewest number of guards."
• P3, S2: The info about the "rotation of 360˚" is still unclear. Explain that while the guards' position will not change, they are able to look in every direction for a potential range of 360˚ from their position.
• The graphic needs a caption with a description of what is happening. The yellow area looks like the appropriate field of view for the first guard. The blue and purple areas do not. I like how the yellow and blue represent the places where the first two guards would be most strategically located. What about continuing that pattern with the third drawing?

--Chris 09:53, 11 July 2013 (EDT) *P4S3: Change "walls" to "area." Check the next sentence to make sure readers clearly understand the concept.

#### An Art Gallery Problem

Chris 11:26, 8 July 2013 (EDT) I wouldn't make a separate heading here. I would simply say: Written in mathematical terms: "For all polygonal-shaped…"

--Chris 09:53, 11 July 2013 (EDT) Remove "and necessary" from the phrase "sufficient and necessary." I also removed the necessary clause when I state Chvatal's theorem in the section below --Lpeng1 16:40, 11 July 2013 (EDT)

## More Mathematical Explanation

### Chvatal's Art Gallery Theorem

Chris 11:26, 8 July 2013 (EDT)

• P2, S1: I think that 'cover' means to see all the area inside the polygon, not all sides of the polygon. I would leave out the 360˚ here.
• P3, S1: Shorten to "We will now delve into the specifics of proving this theorem." Make a smoother transition to Fisk and give the reader a little intro about the fact that concepts such as triangulation, three-coloring, and ears have to be understood before a formal proof can be undertaken.

### Definition of a Polygon

Chris 11:26, 8 July 2013 (EDT)

• P1, S2: This sentence can be omitted.
• You still need to add the section about convex and concave polygons.

--Chris 10:14, 11 July 2013 (EDT) Wait until the end of your page to mention that Libeskind needs only 6 guards. I explicitly removed the statement that the Libeskind needs only 6 guards, but I want to keep my paragraph explaining sufficiency, so I said less guards are sufficient. --Lpeng1 16:43, 11 July 2013 (EDT)

### Triangulation of Polygons

• Your first figure shows one component polygon in the triangulation process; your second shows the entire triangulation. Save the sentence: "Such a polygon is [said to] be triangulated" for later.
• Before you go on to the Proposition that every triangulation uses n-3 diagonals and contains n-2 triangles, give specific information about the numbers of diagonals and triangles for your triangulated Libeskind building.

Proposition: Every triangulation of an n-sided polygon…

Proof

This needs graphics to help the reader understand it.

### Ears of Polygons

--Chris 10:14, 11 July 2013 (EDT) Help the reader understand why this is important to your proof. 1. Explain Graph Theory 2. Prove what you need to prove, keeping the purpose in mind and making it clear to the reader.

#### Meister's Two Ears Theorem

--Chris 10:14, 11 July 2013 (EDT) *It's n>3, not n≥3.

• Do you want to mention Meister at all here? (also Fisk later?)

I like the edits you made to the proof, but parts of it could still be stronger. I wonder if you actually need to use the graph theory proof at all, or if you could use the theory based on the pigeon-hole principle, for which you've already done most of the work. That is, we know any triangulation of a polygon with n sides will consist of n - 2 triangles. By the properties of triangulation, every side of the polygon must also be a side of a triangle. So by the pigeon-hole principle, since the polygon has n sides, and there are n - 2 triangles, at least two triangles must share two sides with the polygon, for any n > 3. (That's the gist, clearly not a full proof, but the whole thing can still be quite short.)

I realize you use graph theory for the rest of your proofs, and so the graph theory proof perhaps "fits" better with the page, but the pigeon-hole proof is much simpler and certainly easier for readers to understand. Since you don't actually use the graph theory elements of the ears proof in later parts of the page, I think it's ok to put aside graph theory for a minute here. It is also a very short proof, so it wouldn't take much time to switch it in for the one you currently have.

-Diana 16:06, 17 July 2013 (EDT)

Some comments on this proof. Most of them center around just making sure your definitions and terms are accurate, non-trivial, and focused on the goal of the proof. One larger issue, though, is that it isn't entirely clear how your critical claim, starting after "then it has at least 2 leaves..." is necessarily true for all polygons, not just the one shown. Try to be more explicit about the aspects of the triangulation proof that you're relying on in that section, and I think it will become more clear that your claim applies to the general case.</font>

For a graph $G$ with a finite set of vertices and edges, denoted by $(V, E)$ If you're going to create these symbolic definitions, use them. If you aren't going to use them, you don't need to define them. respectively, there exists a walk where each pair of consecutive vertices form edges This is unclear. You haven't defined anything that "consecutive" would mean here. In general, we might define a walk as a series of vertices such that each pair of consecutive vertices defines an edge. Also - and this is more important than it sounds - the word "where" in this sentence would need to be "if". The walk is connected A walk is connected by definition. Do you mean to say that a graph is connected if there exists a walk between every pair of vertices? If so, it's actually very important that this applies to any pair of vertices, not just consecutive ones in a walk. if every pair of consecutive vertices forms a walk. Sometimes walks can form cycles, in which case all consecutive vertices are connected, including the initial and end vertices A better definition of a cycle uses the idea of closure; a walk is closed if its first vertex and its last vertex are the same. A closed walk is called a cycle..

From these definitions, <s>we can state that a tree is</s>we can define a tree as a graph that is connected and has a walk. However, a tree does not have cycles, meaning that its start and end vertices do not connect. The converse of what I mentioned above is true; a connected graph by definition has at least one walk. I think what you may want to say is that a tree is 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 <s>only connect to one other adjacent</s>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 expand its whats? illustrations to include dual tree graphs ($D_g$). Such graphs are created by placing a red Why red? vertex within the interior of each triangulation By your earlier definitions, it seems that a "triangulation" refers to the total triangulation of the larger polygon, not the individual triangles within it.. Vertices are connected by an edge to indicate that they are within triangulations which share a non-crossing diagonal of the original polygon, $P$. 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. This is plausible in the figure below, for $D_g$ of the 24-sided Libeskind polygon, by $m=n-1$has 22 vertices by 21 available edges. (Interestingly enough, these numbers mimic the number of triangulations and diagonals of $P$, respectively. This is actually just true by design; a vertex must exist for every triangle, and an edge must exist for every non-intersecting diagonal.) In fact, $D_g$ of $P$ below has two leaves, located at both ends what do you mean by "ends"? I mean, it's easy to see in your image, but the term "ends" is hard to intuitively extend to all other polygons of the triangulated polygons. The locations of the leaves is noteworthy. We allow the leaves to represent ears. By what has been established about leaves, they are only found within disjoint triangulations I think this should be "triangles with disjoint interiors"?. Those disjoint triangulations become the non-overlapping ears of the original polygon, $P$.

-Diana 18:16, 11 July 2013 (EDT)</s>

### Colorings of Triangulated Polygons

--Chris 10:14, 11 July 2013 (EDT) *Explain 3-coloring before you state the theorem or the proof.

• Connect the 3-coloring of vertices to the concept of coverage.

Chris, 1 July 2013 (EDT)Best induction proof I've seen: http://www.cs.princeton.edu/courses/archive/spring12/cos423/bib/tri.pdf

Another good resource for making sense of the Art Gallery Theorem is http://www.docstoc.com/docs/879550/The-Art-Gallery-Problem