Chapter 23
Triangulating the Interior of a Convex Polygon
At this point we return to the problem mentioned at the start, in Chapter 18.
Example 23.1: For n ≥ 1, we start with a convex polygon P of n + 2 sides. We want to count the number of ways n − 1 diagonals can be drawn within the interior of P so that
(i) no two diagonals intersect within the interior of P; and,
(ii) the diagonals partition the interior of P into n triangles—hence, the verb, triangulate.
To show that Cn is the number of ways the interior of a convex (n + 2)-gon can be triangulated, we shall develop a one-to-one correspondence, for when n = 3, with the results in Table 20.2 (in Example 20.3). The method given here was developed in 1961 by Henry George Forder of the University of Auckland in New Zealand. His method is developed in Reference [13].
We replace x0, x1, x2, and x3 in Table 20.2 with a, b, c, and d, respectively. In Fig. 23.1, we find the five ways one can triangulate the interior of a convex pentagon with no intersecting diagonals. In each part, we have labeled four of the sides—with the letters a, b, c, 193 d—as well as all five of the vertices. In part (a), for example, the labels on sides a and b are used to provide the label ab on the diagonal connecting vertices 2 and 4. This is due to the fact that the diagonal ab, together with the sides a and b, provides the leftmost interior triangle in the triangulation of the given convex pentagon. Then the diagonal ab and the side c provide the label ...
