# Talk:Art Gallery Theorem

(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)

# Final Edits

--Chris 12:25, 22 July 2013 (EDT)

• Label all of your graphics—"FIgure 1", "Figure 2", etc.

Yup I labeled all my graphics and included captions which once used to be in the text. The labels might be subject to change as I add more graphics for some of the proofs. --Lpeng1 11:06, 23 July 2013 (EDT)

## Basic Description

• Make "cover" a mouseover with definition from later in the piece. Read all of your uses of the word "cover" in the piece to make sure that you consistently use "cover" to mean the same thing.

## A More Mathematical Explanation

### Chvátal's Theorem

• n>3, remove P2

I removed P2, but am confused as to why I should remove n>3. But doesn't the theorem hold true for a triangle with $n \geq 3$ sides? --Lpeng1 11:06, 23 July 2013 (EDT)

### Definition of a Polygon

• need mouseover for "simple" polygon Done
• P4:
• Make "reflex angle" a mouseover. Change plural to singular. Done
• You introduce "sufficiency" but don't define it. It needs an immediate definition.
• P5, S2: You basically repeat what you said in the last sentence of P4. I'd remove the last sectence of P4 and move the graphic below P5. Explain in more detail why this particular polygon needs 8 guards; you might show a couple sight lines to support your point.

### Triangulation of Polygons

Proof:

• Are you going to add a graphic to support this text?
• How did you get "j+k+5" for the diagonals proof?

### Ears of Polygons

• Is there such a thing as "overlapping ears"? If so, could you give an example?
• Meister's Two Ears Theorem
• P1:
• Make a mouseover for "walk."
• Make both "connected" and "cycles" bold. Done ----
• Images would really help to:
• distinguish connected from non-connected graphs;
• show a graph with a cycle;
• show the relationship between edges and vertices for a tree.
• P2: Bold "tree".Done --Lpeng1 11:06, 23 July 2013 (EDT)
• P3:
• What is a "dual tree graph?" Why dual?
• P4
• S6: "by definition of a tree, they are not equal…" What does equal mean here? They could be congruent and they would still be leaves.
• "..and cannot connect to each other." They do not connect; I don't know that they cannot.

### Fisk's Short Proof

• P1,S1 Give an introduction that relates this to the theorem rather than sending the reader back to Section 1.1.
• The last sentence wraps things up very abruptly. What happened to the discussion about "necessary" vs "sufficient?" Are you omitting this? If so, there should at least be an explanation of how in some cases the minimum is less than the n/3 proven by Fisk's Short Proof and why the Libeskind Building is an example of this kind of case. You may need to reintroduce the "crown" polygon to demonstrate this.

# Response to Checklist

## Messages to the Future

Although this page was meant to cover the basic art gallery problem, other complex variations exist. Future math imagers could consider adding to variations of the problem, such as the orthogonal art gallery theorem. However, extensions could come at the expense of detracting from the essentials of the page.

My page relies on concepts of graph theory to explain the proofs. So additional helper pages on concepts such as 3-coloring, trees/leaves could be helpful to create in the future.

## References and Footnotes

All the images were created by me. I still need to contact the photography studio responsible for taking the aerial shot of the Liebskind building.

All references are included at the end of the page, with direct links to pdf files. I didn’t include footnotes.

## Good Writing

### Context

Tried to generate interest by incorporating the Liebskind Building, a real-life museum, into the page and how the theorem could apply to it.

### Quality of Prose and Page Structuring

Beginning paragraph addresses the problem of finding the minimum number of guards needed to protect a polygonal shaped museum. However, the beginning paragraph doesn’t preview any conclusions, ie. give an exact number of minimum guards for the Liebskind building. This is because there needs to be a further discussion on the nature of the polygonal-shape influencing the minimum number of guards.

Purpose of each section is to consecutively build up concepts needed for Fisk’s short proof, which directly addresses Chavtal’s art gallery problem.

The subsection, Meister’s Two Ears Theorem, has graph theory concepts such as 3 coloring, trees/leaves fundamental to its proof that could be created into future helper pages?

Within the More Mathematical Section, proofs are hidden. However, propositions are fundamental and non-hidden because they build upon each other and get used in Fisk’s short proof.

### Integration of Images and Text

Images and text are evenly integrated throughout the page. Images tend to follow after text. And the text is explicit about the illustrations ‘down below. Would it be helpful to label illustrations instead of saying, referring to the illustration ‘down below’?

### Connections to other Mathematical Topics

Relationships to other mathematical topics could be better explained.

Again, the subsection, Meister’s Two Ears Theorem, has graph theory concepts such as 3 coloring, trees/leaves fundamental to its proof that could be created into future helper pages?

### Examples, Calculations, Applications, Proofs

The images of the Liebskind building demonstrate concepts such as triangulation, 3 coloring, Meister’s Two Ears Thm.

Proofs are obviously included after propositions that are being made

### Mathematical Accuracy and Precision of Language

I’m not sure if all the terminology that I included is accurate. For instance, Diana said she was still confused about the distinction of triangulation of the entire polygon vs. triangulations (smaller triangles being created inside the polygon). Can triangulations be plural and referred to that way? Still need to check up on that…

### Layout

Text is presented in short paragraphs and broken up by images throughout.

Hide features used for the proofs to reduce clutter and scariness. Would it help for the terms to be defined using mouseover? I feel like the way boldfaced terms are defined in the text helps move concepts forward in the page though…

There is weird computer text under the 3-colorable proof if it hasn’t been expanded.

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

Hi Diana,

I initially had a short proof using only the Pigeonhole Principle but Steve M found it confusing. I thought I could better explain the proof using Graph Theory. I have a copy of the proof using only the Pigeonhole Principle stored somewhere, I'll be happy to email it for you to look at, if you believe that works better.

~Lucy

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