Prove that every simple polygon has a ear without resorting to triangulation

Question

We can establish the existence of a triangulation for each simple polygon relying on the fact that every simple polygon has at least one ear, utilizing induction.

Conversely, we can establish that every simple polygon has 2 ears based on triangulation, since every simple polygon with $n$ edges can be triangulated into $n-2$ triangles, where each triangle shares at most 2 edges with the polygon.

My question is: Can we prove that every polygon has a ear without resorting to triangulation?

Answer 1

Yes. We'll prove a stronger claim by induction:

For every simple polygon $P$, and every side $AB$ of that polygon, $P$ has an ear whose central vertex is neither $A$ nor $B$.

(By finding one ear, then applying this claim with one side of the first ear as our $AB$, this gives us the second ear, so in fact this claim directly shows that every polygon has two ears without proving triangulation as a lemma.)

The claim is obvious for triangles.

Now suppose we've shown it up to $(n-1)$-gons, and take $P$ to have vertices $P_1, P_2, P_3, P_4, \ldots, P_n$ in cyclic order. We'll take $A,B=P_1,P_2$ without loss of generality, so we want to find an ear somewhere on $P_3,\ldots,P_n$.

Since every polygon has at least three convex angles, there's at least one other vertex $P_k$ with a convex angle. If $C$ is the vertex of an ear, we're done; otherwise, there is at least one point within the interior of the triangle $\Delta P_{k-1}P_kP_{k+1}$. Choose one such point $P_j$ such that the line from $P_k$ to $P_j$ is fully within the polygon.*

Now, cut our polygon in two along the line segment $P_kP_j$ (by assumption, $j$ wasn't $k-1$ or $k+1$, so these two pieces really are nontrivial polygons). AB will be on one of these two pieces; consider the other piece. By the inductive hypothesis, that piece has an ear disjoint from $P_kP_j$. But that ear is also an ear of the original polygon and is not on AB, so we're done!

*It's not immediately obvious that this is possible, because it might be the case that any point we try to reach in the triangle is separated from us by a squiggle in the boundary of our polygon. But it turns out we can always do this: just choose the point $P_j$ in the interior of the triangle which is closest to $P_k$ along the axis orthogonal to $\overline{P_{k-1}P_{k+1}}$. If an edge of the polygon were to cross over the line segment $P_kP_j$ and interrupt our path, then one side of that edge would have to be even closer to $P_k$, which is a contradiction.

Answer 2

Yes. If angle ABC where A,B,C are consecutive vertices of polygon is convex ( smaller than 180 deg) then B is ear directly from definition of convex set

Answer 3

If the polygon is a triangle, then it is an ear.

Otherwise, the polygon has a diagonal. That diagonal divides the polygon into two disjoint polygons. By induction on the number of vertices, these two parts have ears.