The two-ear theorem was developed and proved by Gary H. Meisters in 1975.

**Ear**

A principal vertex *p _{i}* of a simple polygon

**Examples of Ear(s)**

**Theorem*** *
*Except for triangles, every simple polygon has at least two non-overlapping
ears.*

**Meisters' Proof**

The proof is by Induction on the number of vertices, n, in the simple polygon, P.

**Base case**

When n = 4. The simple polygon is a quadrilateral and has two ears, E1 and E2, as shown below.

**Induction**

Let *P* be a simple polygon with at
least 4 vertices. Consider vertex *p _{i}* is a vertex of

There are two case. Either polygon P has an ear at vertex pi or it does not (i.e. P does not have ear at an ear at vertex, pi).

**Case 1
**Polygon *P* has an ear at *p _{i}*.
If this ear is removed, the resulting polygon

**Case 2
**Polygon *P* does not have an ear at *p _{i}*.
So, the triangle formed by

Let *a* and *b* be the points of
intersection of line *L* with the polygon edges (*p _{i}*,

The line segment *Q* from vertex *q*
to *p _{i}* can be constructed without intersecting any edges of

**There are two sub-cases of
case 2.**

**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

**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

This completes the proof.

**An O( kn)-time Algorithm**

Following algorithm finds an
ear in the
simple polygon *P* :

AlogrithmFindEar(P)

1.i= 0

2. ear not found = true

3.whileear not found

4.ifpis convex_{i}then

5.iftrianglep_{i-1},p, and_{i}p_{i+1}contains no concave vertexthen

6. ear not found = false

7.ifear not foundthen

8.i=i+ 1

9.returnp_{i}

**Correctness [2]**

By the
Two-Ears Theorem, simple polygon *P* has at least 2 ears if the number
of vertices is > 3. If the number of vertices is 3, then *P* is a triangle
and forms 1 ear. By the definition of a
polygon, there is always at least 1 ear in *P* for the algorithm to
find.

To complete the proof of correctness, it suffices to prove the following lemma :

**Lemma**
*If a convex vertex p _{i} is not an ear, then
the triangle formed by p*

*Proof *

If *p _{i}* is not an ear, then the triangle
formed by

This completes the proof of correctness.

Clearly, lines 1 and 2 run in constant time. The loop in line 3 is executed
at most *n* - 2 times, which occurs when *P* has only 2 ears and is
similar to this :

The starting vertex of above algorithm is *p*_{0}. (i=0 at
line 1). If the vertices are sorted in clockwise order, the algorithm would find
first ear shown in yellow. The number of vertices scanned to find this ear is *n* - 2, where *n*
is the number of vertices in *P*. Obviously, line 4 runs in constant time. Line 5 may require O(*k*) time
where *k* - 1 is the number of concave vertices in *P* since it is
possible that all concave vertices are checked for being in triangle (*p*_{i-1},
*p _{i}*,

**An O( n)-time Algorithm**

This recursive algorithm was proposed by Hossam ElGindy and Godfried T. Toussaint.

The input of the algorithm is a
good sub-polygon *GSP* and a vertex *p _{i}*. Initially,
the algorithm

AlgorithmFindAnEar(GSP,p)_{i}

1.ifpis an ear_{i}then

2.returnp_{i}

3. Find a vertexpsuch that (_{j}p,_{i}p) is a diagonal of_{j}GSP.

LetGSP'be the good sub-polygon ofGSPformed by (p,_{i}p)._{j}

Re-label the vertices ofGSP'so thatp=_{i}p_{0}andp=_{j}p_{k-1}

(orp=_{j}p_{0}andp=_{i}p_{k-1}as appropriate) wherekis the number

of vertices ofGSP'.

4.FindAnEar(GSP', floor(k/2))

The correctness of the algorithm depends upon the following three Lemmas 1, 2, and 3.

**Lemma 1 **

*Proof*

Let (*p _{i}*,

This completes the proof of lemma 1.

**Lemma 2 ***
A
diagonal of a good sub-polygon GSP splits GSP into one good
sub-polygon and one sub-polygon that is not good.
*

*Proof*

*GSP* contains exactly one edge, the cutting edge, which
is not an edge of *P*. The cutting edge is entirely contained in one of
the sub-polygons formed by the diagonal. Then the other sub-polygon is a good
sub-polygon since it consists of edges of *P* and the diagonal which
becomes its cutting edge.

This completes the proof of lemma 2.

**Lemma 3 **
*If vertex p _{i} is not an ear then there
exists a vertex p_{j} such that (p_{i}, p_{j})
is a diagonal of P.*

*Proof *

Given a vertex *p _{i}* which is not an ear we
will show how to find a vertex

Let *R* = {*p _{r}* in

**Case 1 ***When p _{i}* is a
convex vertex.

Since

**Case 2 ***When p _{i}* is not a convex vertex.

Since

This completes the proof of lemma 3.

**This completes the proof of correctness.**

Line 1 of __FindAnEar__ can be done in O(*n*) time where *n* is
the number of vertices in *GSP*. Line 2 takes constant time. Line 3 can be
done in O(*n*) time as well.
On the first two calls to __FindAnEar__, *GSP* has O(*n*) vertices.
Consider any subsequent call. Let *k* be the number of vertices in *GSP*.
We have *i* = floor(*k*/2) and (*p*_{0}, *p*_{k-1})
the cutting edge of *GSP*. Consider line 3. If 0 <= *j* <= *i*-2
then *GSP'* = (*p _{j}*,

[1] ElGindy, H., H. Everett, and G.T. Toussaint,** **Slicing an
ear using prune-and-search, *Pattern Recognition Letters*. September
1993, 719-722.

[2] Kong, X., H. Everett, and G.T. Toussaint, The
Graham scan triangulates simple polygons, *Pattern Recognition Letters*.
November 1990, 713-716.