Function 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 formed by 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
End FindEar

Proof of Correctness [3] :

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.

Q.E.D.

Q.E.D.

Time Analysis:

Lines 1 and 2 of FindEar 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 start vertex for FindEar is p₀. If the vertices are sorted in clockwise order, the ear shown in yellow is the first ear found. The number of vertices checked in order to find this ear is n - 2 (where n is the number of vertices in P).

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.

So, since line 5 may be executed in time proportional to n, algorithm FindEar runs in O(kn) time. However, since k - 1 is the number of concave vertices, the algorithm can be as bad as O(n²).