The
Two-Ears Theorem

The Two-Ears Theorem was
developed and proven by Gary
H. Meisters at the University of Nebraska
in 1975 [4].

### The Two-Ears Theorem:

### Proof #1: By Gary H. Meisters

The proof by Meisters is
by induction on the number of vertices, *n*, in the simple
polygon *P*. It is quite elegant.

**Base Case:**

*n* = 4. The simple
polygon *P* is a quadrilateral, which has two ears.

**Induction:**

Let *P* be a simple
polygon with at least 4 vertices. Vertex *p*_{i} is a vertex
of *P* where the interior angle formed by *p*_{i}_{-1},
*p*_{i}, and *p*_{i}_{+1} is less than
180^{o}.

**Case 1:**

Polygon *P* has an
ear at *p*_{i}. If this ear is removed, the remaining polygon
*P'* is a simple polygon with more than three vertices, but with one
less vertex than *P*. By the induction hypothesis, there are two non-overlapping
ears *E*_{1} and *E*_{2} for *P'*. Since
they are non-overlapping, at least one of these two ears, say *E*_{1},
is not at either of the vertices *p*_{i}_{-1} or *p*_{i}_{+1}.
Since all ears of *P'* are also ears of *P*, polygon *P*
has two ears: *E*_{1} and the ear at *p*_{i}.

**Case 2:**

Polygon *P* does not
have an ear at *p*_{i}. So, the triangle formed by *p*_{i}_{-1},
*p*_{i}, and *p*_{i}_{+1} contains at
least one vertex of *P* in its interior. Let *q* be the vertex
in the interior of this triangle such that the line *L* through *q*
and parallel to the line through *p*_{i}_{-1} and
*p*_{i}_{+1} is as close to *p*_{i} as
possible.

Let *a* and *b*
be the points of intersection of line *L* with the polygon edges (*p*_{i},
*p*_{i}_{+1}) and (*p*_{i}_{-1},
*p*_{i}), respectively. The triangle formed by *p*_{i},
*a*, and *b* does not contain in its interior any vertex of *P*
(or else our choice of vertex *q* would be incorrect).

The line segment *Q*
from vertex *q* to *p*_{i} can be constructed without
intersecting any edges of *P*. Line segment *Q* divides *P*
into two simple polygons: *P*_{1} (that contains vertices
*p*_{i}, *p*_{i}_{+1},..., *q*)
and *P*_{2} (that contains vertices *p*_{i},
*p*_{i}_{-1},..., *q*).

**Case 2a:**

Polygon *P*_{1}
is a triangle. So, *P*_{1} is an ear for polygon *P*.
By the induction hypothesis, polygon *P*_{2} must have at
least two non-overlapping ears, *E*_{1} and *E*_{2}
(or else it too would be a triangle and polygon *P* would have only
four vertices). Since they are non-overlapping, at least one, say *E*_{1},
is at neither vertices *p*_{i} nor *q*. *E*_{1}
does not overlap with the ear formed by polygon *P*_{1}, so
it is the second ear in polygon *P*.

**Case 2b:**

Polygon *P*_{1}
is not a triangle. So, by the induction hypothesis, polygon *P*_{1}
has two ears, *E*_{11} and *E*_{12} and polygon
*P*_{2} has two ears, *E*_{21} and *E*_{22}.
Since they are non-overlapping, at least one of the ears in *P*_{1},
say *E*_{11}, is not at vertex *p*_{i} or *q*.
Similarly, at least one of the ears in *P*_{2}, say *E*_{21},
is not at vertex *p*_{i} or *q*. These two ears, *E*_{11}
and *E*_{21} will be non-overlapping ears for polygon *P*

It is known that a simple
polygon can always be triangulated.
Leaves in the dual-tree
of the triangulated polygon correspond to ears and every tree of two or
more nodes must have at least two leaves.

### Some Examples:

`This page was last updated on Wednesday, December 10`^{th},
1997.

`©` `1997 Ian Inc.`