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₀ and p_j = p_k-1
     (or p_j = p₀ 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_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

Q.E.D.

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