An O(n) Time Algorithm for Finding an Ear

A recursive algorithm was developed by Hossam ElGindy at the University of Newcastle, Hazel Everett at the Université du Québec, and Godfried T. Toussaint at McGill University [1].

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

Function FindAnEar(GSP, pi)
1.  if pi is an ear then
2.      return pi
3.  Find a vertex pj such that (pi, pj) is a diagonal of GSP.
Let GSP' be the good sub-polygon of GSP formed by (pi, pj).
Re-label the vertices of GSP' so that pi = p0 and pj = pk-1
(or pj = p0 and pi = pk-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 (pi, pj) be the cutting edge of GSP. By the Two-Ears Theorem GSP has at least two non-overlapping ears. Vertices pi and pj 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 pi is not an ear then there exists a vertex pj such that (pi, pj) is a diagonal of P.

Proof: Given a vertex pi which is not an ear we will show how to find a vertex pj such that (pi, pj) is a diagonal. Construct a ray, ray(pi), at pi that bisects the interior of angle (pi-1, pi, pi+1). Find the first intersection point of ray(pi) with the boundary of P. Note that this is done simply by testing each edge of the polygon for intersection with ray(pi). Let y be the intersection point on edge (pk, pk+1). Point y must exist and y <> pi-1 or pi+1. Note that the line segment (pi, y) lies entirely inside P. Thus if y is a vertex then (pi, y) is a diagonal. Suppose y is not a vertex. Then pk+1 and pi-1 lie in one of the half-planes defined by ray(pi), and pk and pi+1 lie in the other. We will show that if triangle (pi, y, pk+1) does not contain a vertex pj such that (pi, pj) is a diagonal of P then triangle (pi, y, pk) does.

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

Case 1: pi is a convex vertex.

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

Case 2: pi is not a convex vertex.

Since z = pi-1 , pk does not lie between rays piy and pi pi-1. Similarly, pk+1 does not lie between rays pi y and pi pi+1. Since pk+1 lies in the same half-plane defined by ray(pi) as pi-1, and pk and pi+1 lie in the other there is no place for segment pkpk+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 (p0, pk-1) the cutting edge of GSP. Consider line 3. If 0 <= j <= i-2 then GSP' = (pj, pj+1, ..., pi). Otherwise, i+2 <= j <= k-1 and GSP' = (pi, pi+1, ..., pj). In either case, GSP' contains no more than floor(k/2) + 1 vertices.