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**
*p _{i}* is
convex

5.

6. ear not found = false

7.

8.

9.

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

**Proof:** If *p _{i}* is not an ear, then the triangle
formed by

Q.E.D.

The proof of correctness for algorithmQ.E.D.

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*_{0}. 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}*,

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*^{2}).

`This page was last updated on Wednesday, December 10 ^{th},
1997.`

`©` `1997 Ian Inc.`