**Function** __FindAnEar__(*GSP*, *p*_{i})

1. **if** *p*_{i} is an ear **then**

2. **return** *p*_{i}

3. Find a vertex *p*_{j} such that
(*p*_{i}, *p*_{j}) is a diagonal of
*GSP*.

Let *GSP'* be the good sub-polygon of *GSP*
formed by
(*p*_{i}, *p*_{j}).

Re-label the vertices of
*GSP'* so that *p*_{i} = *p*_{0} and
*p*_{j} = *p*_{k-1}

(or *p*_{j} =
*p*_{0} and *p*_{i} = *p*_{k-1}
as appropriate) where *k* is the number

of vertices of *GSP'*.

4. __FindAnEar__(*GSP'*, floor(*k*/2))

**End** __FindAnEar__

### Proof of Correctness
[1] :

The correctness of the algorithm follows from Lemmas 1, 2, and 3.

**Lemma 1:** A
good sub-polygon
has at least one
proper ear.

**Proof:** Let (*p*_{i}, *p*_{j}) be the
cutting edge of *GSP*. By the
Two-Ears Theorem *GSP* has at
least two non-overlapping ears. Vertices *p*_{i} and
*p*_{j} cannot be the only ears of *GSP* since these
would overlap. Thus some other vertex of *GSP* is an ear and it is
a proper ear.

Q.E.D.

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

Q.E.D.

**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 *p*_{j} such that
(*p*_{i}, *p*_{j}) is a diagonal. Construct a
ray, *ray*(*p*_{i}), at *p*_{i} that
bisects the interior of angle (*p*_{i-1},
*p*_{i}, *p*_{i+1}). Find the first
intersection point of *ray*(*p*_{i}) with the boundary
of *P*. Note that this is done simply by testing each edge of the
polygon for intersection with *ray*(*p*_{i}). Let
*y* be the intersection point on edge (*p*_{k},
*p*_{k+1}). Point *y* must exist and *y* <>
*p*_{i-1} or *p*_{i+1}. Note that the
line segment (*p*_{i}, *y*) lies entirely inside *P*.
Thus if *y* is a vertex then (*p*_{i}, *y*) is a
diagonal. Suppose *y* is not a vertex. Then *p*_{k+1}
and *p*_{i-1} lie in one of the half-planes defined by
*ray*(*p*_{i}), and *p*_{k} and
*p*_{i+1} lie in the other. We will show that if triangle
(*p*_{i}, *y*, *p*_{k+1}) does not
contain a vertex *p*_{j} such that (*p*_{i},
*p*_{j}) is a diagonal of *P* then triangle
(*p*_{i}, *y*, *p*_{k}) does.

Let *R* = {*p*_{r} in *P* such that *p*_{r}
lies in triangle (*p*_{i}, *y*,
*p*_{k+1}), *k*+1 < *r* < *i*}. If
*R* = NULL then by the
Jordan Curve Theorem and the fact that line
segment (*p*_{i}, *y*) lies entirely inside *P*,
the interior of triangle (*p*_{i}, *y*,
*p*_{k+1}) is empty. If *p*_{k+1} <>
*p*_{i-1} then (*p*_{i},
*p*_{k+1}) is a diagonal. Otherwise let *z* =
*p*_{i-1}. If *R* = NULL then for all *p*_{r}
in *R* compute angle (*y*, *p*_{i}, *p*_{r})
and let *z* be the vertex that minimizes this angle. By choice of
*z*, the interior of triangle (*p*_{i}, *y*,
*z*) is empty. Thus if *z* <> *p*_{i-1} then
(*p*_{i}, *z*) is a diagonal. Hence if no diagonal
has been found thus far then *z* = *p*_{i-1}.
Similarly define *S* = {*p*_{s} in *P* such that
*p*_{s} lies in triangle (*p*_{i}, *y*,
*p*_{k}), *i* < *s* < *k*}. If *S* =
NULL, the interior of triangle (*p*_{i}, *y*,
*p*_{k}) is empty and if *p*_{k} <>
*p*_{i+1} then (*p*_{i}, *p*_{k})
is a diagonal. Define *w* analogously to *z*; that is, either
*w* = *p*_{i+1} or *w* is the vertex that
minimizes angle (*y*, *p*_{i}, *p*_{s}).
By choice of *w* the interior of triangle (*p*_{i},
*y*, *w*) is empty. We will show that *w* <>
*p*_{i+1} and then it follows that (*p*_{i},
*w*) is a diagonal. Recall that *z* = *p*_{i-1}
so that triangle (*p*_{i}, *y*,
*p*_{i-1}) is empty. Assume that *w* =
*p*_{i+1} so that triangle (*p*_{i}, *y*,
*p*_{i+1}) is empty.

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

Since *p*_{i} is not an ear, at least one vertex of
*P* lies in triangle (*p*_{i-1}, *p*_{i},
*p*_{i+1}). Suppose *y* lies outside of triangle
(*p*_{i-1}, *p*_{i},
*p*_{i+1}).
Since triangle (*p*_{i}, *y*, *p*_{i-1})
and triangle (*p*_{i}, *y*, *p*_{i+1})
are empty then so is (*p*_{i-1}, *p*_{i},
*p*_{i+1}) which is a contradiction. Suppose *y* lies
inside of triangle (*p*_{i-1}, *p*_{i},
*p*_{i+1}). Since triangle (*p*_{i},
*y*, *p*_{i-1}) is empty, *p*_{k+1}
does not lie in triangle (*p*_{i}, *y*,
*p*_{i-1}). Similarly, *p*_{k} does not lie
in triangle (*p*_{i}, *y*, *p*_{i+1}).
But then there is no place for segment *p*_{k}
*p*_{k+1}.

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

Since *z* = *p*_{i-1} , *p*_{k} does not
lie between rays *p*_{i}*y* and *p*_{i}
*p*_{i-1}. Similarly, *p*_{k+1} does
not lie between rays *p*_{i} *y* and
*p*_{i} *p*_{i+1}. Since *p*_{k+1}
lies in the same
half-plane defined by *ray*(*p*_{i}) as
*p*_{i-1}, and *p*_{k} and
*p*_{i+1}
lie in the other there is no place for segment
*p*_{k}*p*_{k+1}
Q.E.D.

The proof of correctness for algorithm __FindAnEar__ is complete.
Q.E.D.

### Time Analysis
[1] :

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}, *p*_{j+1}, ...,
*p*_{i}). Otherwise, *i*+2 <= *j* <= *k*-1
and *GSP'* = (*p*_{i}, *p*_{i+1}, ...,
*p*_{j}). In either case, *GSP'* contains no more
than floor(*k*/2) + 1 vertices.