O(kn) Time Algorithm

Contents

Interactive Ear Cutting!


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.

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.


O(kn) Time Algorithm

Contents

Interactive Ear Cutting!



This page was last updated on Wednesday, December 10th, 1997.

© 1997 Ian Inc.