O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 30

Triangulating the Interior of a Convex Polygon for the Second Time

Now it is time to revisit the situation we examined in Example 23.1.

Example 30.1: In this example, we shall take a second look at the problem of determining Tn, the number of ways the interior of a convex polygon of n sides can be triangulated into n − 2 triangles—by drawing n − 3 diagonals, no two of which intersect within the interior.

In Fig. 30.1 30.1 (a), we have a convex polygon with n + 1 sides, where we have drawn the diagonals img and img. These diagonals break up the interior of this convex polygon into three regions: (i) the interior of triangle img; (ii) the interior of triangle img; and (iii) the interior of the (n − 1) -sided convex polygon img. The interior of the first region can be triangulated in T3ways, while there are Tn−1 = T(n+1)−2 ways to triangulate the interior of the third region. Therefore, there are T3T(n+1)−2 ways to triangulate the interior of the given convex polygon with n + 1 sides—where the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required