Alogrithm FindEar(P)
1.  i = 0
2.  ear not found = true
3.  while ear not found
4.      if p_i is convex then
5.          if triangle  p_i-1, p_i, and p_i+1 contains no concave vertex then
6.              ear not found = false
7.      if ear not found then
8.          i = i + 1
9.  return p_i
 

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_i-1, p_i, and p_i+1 contains a concave vertex.

Proof   

If p_i is not an ear, then the triangle formed by p_i-1, p_i, and p_i+1 contains a vertex. Let p_j be the vertex in the interior of this triangle (p_i-1, p_i, p_i+1) such that the line L through p_j 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. Triangle (a, p_i, b) has no vertices in its interior and lies entirely inside P. Vertices p_j-1 and p_j+1 must lie on the opposite side of line L, so p_j is a concave vertex. This completes the proof of lemma.
 

This completes the proof of correctness.

Time Analysis

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₀. (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, p_i+1). Lines 6, 7, 8, and 9 all run in constant time. Since line 5 executed in time proportional to n in the worst case, the algorithm runs in O(kn) time. However, since k - 1 is the number of concave vertices, the algorithm can be as bad as O(n²).

The input of the algorithm is a good sub-polygon GSP and a vertex p_i. Initially, the algorithm FindAnEar is called with the simple polygon P and any vertex of P.

Correctness [1]

The correctness of the algorithm depends upon the following three 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.
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.

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    When 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    When p_i is not a convex vertex.

Since z = p_i-1 , p_k does not lie between rays p_iy 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_kp_k+1
This completes the proof of lemma 3.

This completes the  proof of correctness.

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₀, 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.