Polygon triangulation: recursive algorithm

keep dividing a polygon until all that's left are triangles

The recursive algorithm for triangulating the polygon begins by searching for two vertices  on opposite sides ot the polygon, and connecting them with a diagonal.   If the diagonal lies totally within the polygon, the polygon has been decomposed into two smaller polygons; if not, a pair of vertices is found whose diagonal does lie totally within the polygon.  This procedure is then continued recursively until all smaller polygons are triangles. 

This algorithm is used in the "art gallery problem," found elsewhere. 

Movies

Thirteen movies are available; for polygons of eight (four movies), sixteen (five movies), 32 (two movies) and 64 (two movies) sides.  One of the movies made of the triangulation of a sixteen-sided polygon is accompanied by pauses for questions to the viewer.  Remember the guidelines for use of these movies.