17
$\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$
6
  • 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, 2015 at 19:47
  • 1
    $\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, 2015 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, 2015 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, 2015 at 20:46
  • 2
    $\begingroup$ (@Blue) That there even is a triangulation is non-trivial. $\endgroup$
    – Joseph O'Rourke
    Sep 4, 2015 at 22:14

4 Answers 4

Reset to default
8
$\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$
4
  • $\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, 2015 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, 2015 at 23:13
  • 3
    $\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, 2015 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, 2015 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$
9
  • 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, 2015 at 19:36
  • 1
    $\begingroup$ My mistake; you are right. I will fix. Thanks! $\endgroup$
    – Joseph O'Rourke
    Sep 4, 2015 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, 2015 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, 2015 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, 2015 at 20:34
2
$\begingroup$

This is several years late, but I think I have a nicer proof. I thought I would post it.

Let's believe we can triangulate the 5-gon into three triangles. Note that these three triangles all must have a vertex $v$ in common: To see this, remove one of the triangles $T$, s.t. we have a 4-gon left. Then whichever way we triangulate the 4-gon every edge will contain a vertex from both of its triangles. In particular, the joint edge of $T$ and the 4-gon will have such a vertex $v$.

Then $v$ sees all three triangles and hence the entire 5-gon. enter image description here

$\endgroup$
4
  • $\begingroup$ How does this work with the counterexample suggestion that I put at the end of the original post? It looks like you're claiming there will always be a vertex that can see every other point, which is stronger than my claim; it is also false per the aforementioned figure. Not sure if I've misunderstood your post? $\endgroup$
    – Benjamin Dickman
    Feb 19, 2021 at 1:17
  • 1
    $\begingroup$ @BenjaminDickman I'm not sure which counterexample you're referring to, but certainly, the picture you posted in the Edit isn't an issue. You can see the whole 5-gon from the second vertex from the left. $\endgroup$
    – Misha Schmalian
    Feb 19, 2021 at 17:57
  • $\begingroup$ true, true; very cool! I suppose the missing piece (?) is somehow justifying the belief that you opened with. Or should this be evident? $\endgroup$
    – Benjamin Dickman
    Feb 20, 2021 at 3:21
  • $\begingroup$ @BenjaminDickman sorry for the late reply. It's not completely obvious. But its standard. A quick proof can be found here: flashman.neocities.org/triangulation.html $\endgroup$
    – Misha Schmalian
    Mar 2, 2021 at 10:28
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$
5
  • 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, 2015 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, 2015 at 20:08
  • 2
    $\begingroup$ @BenjaminDickman: This second counterexample is right. I'll try to take it into account. $\endgroup$
    – joriki
    Sep 4, 2015 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, 2015 at 20:11
  • 2
    $\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, 2015 at 3:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .