The Two-Ears Theorem

Contents

O(n) Time Algorithm


An O(kn) Time Algorithm for Finding an Ear


A very simple algorithm exists for finding an ear in the simple polygon P :


Function FindEar(P)
1.  i = 0
2.  ear not found = true
3.  while ear not found
4.      if pi is convex then
5.          if triangle formed by pi-1, pi, and pi+1 contains no concave vertex then
6.              ear not found = false
7.      if ear not found then
8.          i = i + 1
9.  return pi
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 :

Q.E.D.

The proof of correctness for algorithm FindEar is complete.

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 p0. 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 (pi-1, pi, pi+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(n2).


The Two-Ears Theorem

Contents

O(n) Time Algorithm



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

© 1997 Ian Inc.