Question

Give a recursive algorithm for triangulating a simple polygon with n sides, using Lemma 1 in Section 5.2.

Short answer

The recursive algorithm is given

Step-by-step solution

Given that

Given a simple polygon with n sides.

Write algorithm

If n = 3 , then the polygon is already triangulated.

Otherwise, the polygon must have a diagonal. Draw the diagonal. This diagonal splits the polygon into two polygons, each of which has less than n vertices.

Recursively apply this algorithm to triangulate each of these polygons. The result is a triangulation of the original polygon.