14
$\begingroup$

Question: What is a succinct proof that all pentagons are star shaped?

In case the term star shaped (or star convex) is unfamiliar or forgotten:

Definition Reminder: A subset $X$ of $\mathbb{R}^n$ is star shaped if there exists an $x \in X$ such that the line segment from $x$ to any point in $X$ is contained in $X$.

This topic has arisen in the past in my class discussions around interior angle sums; specifically, for star shaped polygons in $\mathbb{R}^2$ we can find their sum of interior angles as follows:

By assumption, there is an interior point $x$ that can be connected to each of the $n$ vertices. Drawing in these line segments, we construct $n$ triangles; summing across all of their interior angles gives a total of $180n^\circ$, but this over-counts the angle sum for the polygon by the $360^\circ$ around $x$. Therefore, the sum of interior angles is $(180n - 360)^\circ = 180(n-2)^\circ$.

This formula for the sum of interior angles holds more generally (often shown by triangulating polygons) but the proof strategy above already fails for some (obviously concave) hexagons.

For example:

enter image description here

The above depicted polygon is not star shaped.

Moreover, it is a fact that any polygon with five or fewer sides is star shaped. And so I re-paste:

Question: What is a succinct proof that all pentagons are star shaped?


Edit: Since it has come up as a counterexample (of sorts) for each of the first two responses, here is an example of a concave pentagon that may be worth examining in thinking through a proof.

enter image description here

$\endgroup$
  • 4
    $\begingroup$ $\lfloor\frac53 \rfloor = 1$. See the Art Gallery Theorem. :) (Okay, it's cheating to sweep all the work into a referenced theorem. However, Steve Fisk was an academic advisor of mine way-back-when, and I think his proof is nice.) $\endgroup$ – Blue Sep 4 '15 at 19:47
  • $\begingroup$ @Blue Yes, as you realize, I am hoping for something more self-contained. The context in which this has come up has been in mathematics content courses for elementary school teachers, and I can't guarantee the inclusion of the Art Gallery Theorem... but maybe I'll have to re-think that! $\endgroup$ – Benjamin Dickman Sep 4 '15 at 19:50
  • $\begingroup$ I added a smiley! :) :) (Besides, you didn't explain the nature of your audience.) Be that as it may ... Fisk's mechanism (triangulate and find an appropriate $3$-coloring of vertices), when restricted to the pentagon, amounts to observing that the two segments used to triangulate a pentagon share a vertex. That fact isn't necessarily immediately obvious, but you likely will have laid appropriate foundations for it in proving the angle-sum theorem via triangulation. $\endgroup$ – Blue Sep 4 '15 at 20:19
  • $\begingroup$ @Blue Ah, but we don't prove (in class) the angle-sum theorem via triangulation. It is stated and demonstrated with examples, and I have followed up with a few curious students about how it can be done using the "ear-cutting" approach -- but concave polygons are a bit subtle. As mentioned earlier: I'll do some thinking about how this part of the curriculum is organized...! :) $\endgroup$ – Benjamin Dickman Sep 4 '15 at 20:46
  • 2
    $\begingroup$ (@Blue) That there even is a triangulation is non-trivial. $\endgroup$ – Joseph O'Rourke Sep 4 '15 at 22:14
7
$\begingroup$
  • Assuming(?!) that every polygon has at least one "convex" vertex, let $P$ such a vertex. $P$ "sees" its two neighbors. If $P$ also "sees" a third vertex, $Q$, then connect them with a segment; otherwise, connect $P$'s neighbors with a segment, and rename those neighbors $P$ and $Q$. Either way, diagonal $\overline{PQ}$ separates the interior of the polygon, and it serves as a side of each piece: a triangle and a quadrilateral.

  • Repeating the above procedure on the quadrilateral, we conclude that one of its diagonals separates its interior (this time, into two triangles). Necessarily, one of the endpoints of that diagonal is either $P$ or $Q$. We'll say that it's $P$.

  • Therefore, $P$ is a vertex of the three sub-triangles, and it can "see" all points in each of those triangles (because triangles are cool like that), which means that it can "see" all points in the original pentagon. $\square$


Note. Of course, you should never assume. A triangle with edges in one hemisphere of a balloon, but an "interior" that contains the other hemisphere, has no "convex" vertices at all. So, this solution is flawed from its very first word. Overcoming the flaw is left as an exercise to the reader.

$\endgroup$
  • $\begingroup$ This approach reminds me of Meisters (1975) in which it is proved that polygons can have two non-overlapping "ears" (triangles) cut out; in this case, that creates three triangles, and a vertex shared by all three: which does the trick, as you note. [The citation is: Meisters, G. H. (1975). Polygons have ears. American Mathematical Monthly, 648-651.] $\endgroup$ – Benjamin Dickman Sep 4 '15 at 23:05
  • 2
    $\begingroup$ Nice proof, Blue! I would say that yours is more convincing to those combinatorially inclined, mine more convincing to those geometrically inclined. Perhaps both should be presented. $\endgroup$ – Joseph O'Rourke Sep 4 '15 at 23:13
  • 2
    $\begingroup$ @BenjaminDickman: Polygons do indeed have ears (Meisters' result is a classic!), but the nice thing about my argument is that I make no assumption about them. It's certainly true that, in a pentagon, the first diagonal I construct does cut off an ear (and so does the second). However, this triangulation strategy is valid with any starting polygon, yet the process isn't guaranteed to clip an ear if that first $P$ sees its $Q$. $\endgroup$ – Blue Sep 4 '15 at 23:33
  • 1
    $\begingroup$ @BenjaminDickman: By accepting this answer, you gave me a reputation score of $23,456$. Thanks! :) (Of course, it'll be more impressive $100$K points from now ...) $\endgroup$ – Blue Sep 5 '15 at 2:37
8
$\begingroup$

(A perhaps more common term than star convex is star-shaped.)

I assume you view the pentagon as a closed set, including its boundary, so that the line of sight from $x$ can touch the boundary and still be "contained."

Here is a proof, maybe still not succinct enough for your purposes. Define a reflex vertex as one at which the internal angle exceeds $180^\circ$. The others are convex vertices.

(1) Any polygon must have at least three convex vertices. Let me take this as given.

(2) Therefore a pentagon $P$ can have at most two reflex vertices.

(3) If $P$ has no reflex vertices, $P$ is convex and easily star-shaped.

(4) If $P$ has one reflex vertex $v$, then $P$ is visible from $v$ and so star-shaped.

(5) If $P$ has two reflex vertices, they are either adjacent or not. If adjacent, then $P$ is visible from the middle convex vertex $v$ and so star-shaped.

(6) If $P$ has two non-adjacent reflex vertices, then let $a,b,c$ be three consecutive vertices, with $a,c$ reflex and $b$ between them convex. Extend the edges $ba$ and $bc$ until they hit the opposite side. Then any point $x$ on that edge between the extensions can see all of $P$:


          StarPentagon


$\endgroup$
  • 1
    $\begingroup$ If $P$ has two reflex vertices they don't need to be adjacent. A third figure is called for ... $\endgroup$ – Christian Blatter Sep 4 '15 at 19:36
  • 1
    $\begingroup$ My mistake; you are right. I will fix. Thanks! $\endgroup$ – Joseph O'Rourke Sep 4 '15 at 19:50
  • 1
    $\begingroup$ Thanks @ChristianBlatter and Benjamin for correcting me. It has become less succinct, but more correct. :-) $\endgroup$ – Joseph O'Rourke Sep 4 '15 at 20:04
  • 2
    $\begingroup$ Incidentally, it is true that one vertex always sees all of $P$, but pinpointing that vertex requires a bit of work. For example, in my 3rd figure, $c$ suffices but $a$ does not, despite their superficial similarity. $\endgroup$ – Joseph O'Rourke Sep 4 '15 at 20:13
  • 1
    $\begingroup$ @BenjaminDickman: Yes, one vertex has this property in a pentagon. But I am not sure how to identify it except by triangulating the pentagon and then arguing from the triangulation. This is essentially what the art gallery theorem does to prove the more general claim. Or one could use the geometry as in my proof. $\endgroup$ – Joseph O'Rourke Sep 4 '15 at 20:34
0
$\begingroup$

A polygon must have at least three convex vertices (since each convex vertex turns by less than $\pi$ and in total the vertices must turn by $2\pi$). Thus there is at least one vertex that is between two convex vertices. This vertex sees all four other vertices, and hence the entire pentagon.

$\endgroup$
  • 1
    $\begingroup$ @Benjamin: You’ve misunderstood: there are no vertices between the leftmost and rightmost vertices in your example. By between joriki means between and adjacent to both. $\endgroup$ – Brian M. Scott Sep 4 '15 at 20:03
  • 1
    $\begingroup$ @BrianM.Scott In the same picture: The lowest and rightmost vertices are both convex; indeed, they have a vertex between them. But it does not see all four other vertices (it can't quite see the leftmost one). Am I still misunderstanding something or are their additional details necessary? (I would ultimately like the "succinct" proof to be presentable to elementary school teachers, so I'd rather err on the side of too many details...) $\endgroup$ – Benjamin Dickman Sep 4 '15 at 20:08
  • 2
    $\begingroup$ @BenjaminDickman: This second counterexample is right. I'll try to take it into account. $\endgroup$ – joriki Sep 4 '15 at 20:10
  • 2
    $\begingroup$ @Benjamin: No, you’re understanding correctly now. It appears that the argument does require a further step. And if the two reflex vertices are adjacent, it’s the convex vertex that is not adjacent to them that sees everything, so there does seem to be a problem. $\endgroup$ – Brian M. Scott Sep 4 '15 at 20:11
  • 1
    $\begingroup$ (I down-voted this response because of the leap in reasoning, but will gladly undo that -- and up-vote! -- if/when it is rectified...) $\endgroup$ – Benjamin Dickman Sep 5 '15 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.