Introduction

Contents

O(kn) Time Algorithm

The Two-Ears Theorem was developed and proven by Gary H. Meisters at the University of Nebraska in 1975 [4].

The Two-Ears Theorem:

Proof #1: By Gary H. Meisters

The proof by Meisters is by induction on the number of vertices, n, in the simple polygon P.   It is quite elegant.

Base Case:

n = 4. The simple polygon P is a quadrilateral, which has two ears.

Induction:

Let P be a simple polygon with at least 4 vertices. Vertex p_i is a vertex of P where the interior angle formed by p_i-1, p_i, and p_i+1 is less than 180^o.

Case 1:

Polygon P has an ear at p_i. If this ear is removed, the remaining polygon P' is a simple polygon with more than three vertices, but with one less vertex than P. By the induction hypothesis, there are two non-overlapping ears E₁ and E₂ for P'. Since they are non-overlapping, at least one of these two ears, say E₁, is not at either of the vertices p_i-1 or p_i+1. Since all ears of P' are also ears of P, polygon P has two ears: E₁ and the ear at p_i.

Case 2:

Polygon P does not have an ear at p_i. So, the triangle formed by p_i-1, p_i, and p_i+1 contains at least one vertex of P in its interior. Let q be the vertex in the interior of this triangle such that the line L through q and parallel to the line through p_i-1 and p_i+1 is as close to p_i as possible.

Let a and b be the points of intersection of line L with the polygon edges (p_i, p_i+1) and (p_i-1, p_i), respectively. The triangle formed by p_i, a, and b does not contain in its interior any vertex of P (or else our choice of vertex q would be incorrect).

The line segment Q from vertex q to p_i can be constructed without intersecting any edges of P. Line segment Q divides P into two simple polygons: P₁ (that contains vertices p_i, p_i+1,..., q) and P₂ (that contains vertices p_i, p_i-1,..., q).

There are now two sub-cases to consider:

Case 2a:

Polygon P₁ is a triangle. So, P₁ is an ear for polygon P. By the induction hypothesis, polygon P₂ must have at least two non-overlapping ears, E₁ and E₂ (or else it too would be a triangle and polygon P would have only four vertices). Since they are non-overlapping, at least one, say E₁, is at neither vertices p_i nor q. E₁ does not overlap with the ear formed by polygon P₁, so it is the second ear in polygon P.

Case 2b:

Polygon P₁ is not a triangle. So, by the induction hypothesis, polygon P₁ has two ears, E₁₁ and E₁₂ and polygon P₂ has two ears, E₂₁ and E₂₂. Since they are non-overlapping, at least one of the ears in P₁, say E₁₁, is not at vertex p_i or q. Similarly, at least one of the ears in P₂, say E₂₁, is not at vertex p_i or q. These two ears, E₁₁ and E₂₁ will be non-overlapping ears for polygon P

Proof #2: By Joseph O'Rourke [6]

It is known that a simple polygon can always be triangulated. Leaves in the dual-tree of the triangulated polygon correspond to ears and every tree of two or more nodes must have at least two leaves.

Some Examples:

Introduction

Contents

O(kn) Time Algorithm