The problem is to find the number of ways of triangulation in a polygon.

Let us first understand what is meant by triangulation of a polygon. Triangulation of a polygon means partitioning the polygon so that each part of the polygon is a triangle. Our aim is to find the number of ways in which this partitioning can be done.

Example :

We take an input ‘N’ from the user for the number of sides of the polygon. Suppose N=5. That means we need to find the number of triangulations in a 5 sided polygon.

A 5 sided polygon is a pentagon. And as we can observe in the image above, there can be only 5 ways to triangulate a pentagon.

Approach

Before we move to the approach to tackle the above problem, it’s essential to understand the Catalan number series. It’s a sequence of numbers formed by the given formula -

Let’s understand through an example.

The Zeroth and the first Catalan numbers are 1 and 1. According to the formula ,The 2nd number is given by C1*C0+C0*C1 = 1*1 + 1*1 = 2. And just like that:-

So, the purpose of learning the Catalan number series was because this problem, at its core, is the Catalan series.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

How is the Catalan series helpful in handling this problem?

We know C_{0}=C_{1}=1. For this scenario, let’s assume C_{2}=C_{3}=1 and the following series starts from C_{2} onwards. The purpose of this assumption was that we assumed 2 vertices could be joined to form only 1 triangle (we know it’s not very intuitive but it’s a necessary assumption to tackle this problem). Similarly, 3 vertices could be joined to form only one single triangle. So essentially, we’ve renamed C_{0} as C_{2} and C_{1} as C_{3}.

Suppose we have a 4 sided polygon, which we know can be triangulated in only 2 ways, as can be seen below.

On joining the opposite vertices of the first rectangle we’ll see that there are 3 points (1, 2, 4) on one side of the construction and 2 points (2,4) on the other. These 3 vertices can be joined in one and only one way to form a triangle, and as per our assumption earlier, 2 points can be used to form a single triangle. Therefore C_{4} = C_{2}.C_{3} + C_{3}.C_{2} in this case.

We know C_{4} = C_{0}.C_{3} + C_{1}.C_{2} + C_{2}.C_{1} + C_{3}.C_{0}. But remember in this case our Catalan series begins with C_{2} instead of C_{0}. So essentially C_{4} would be C_{2} in a regular Catalan series.

And as we saw earlier, a 5 sided polygon can be triangulated in 5 ways which are C_{3} ways.

Therefore it can be deduced that an N-sided polygon can be triangulated in C_{N-2} ways.

Algorithm

The number of ways in which an N-sided polygon can be triangulated is equal to (N-2)th Catalan number. So, we have to find the (N-2)th Catalan Number.

Initialise a dp array of size n to store the results of computations.

Put dp[0] and dp[1] equal to 1. Iterate through the outer loop from i=2 to N.

Iterate the inner loop from j=2 to i-1.

Use the formula dp[i] += dp[j] x dp[i-j-1] in the nested loop to generate and store the catalan series.

Print dp[n-2].

Implementation

defTriangulation(n): dp=[0]*n #Creating an array of input size dp[0]=1#Initialising the first 2 values in the array as 1 dp[1]=1 for i in range(2,n): for j in range(0,i): #Dynamically storing the results as we iterate and making use of previously done computations. dp[i]+=dp[j]*dp[i-j-1]

#Number of triangulations in an n sided polygon is C_{n-2} return dp[n-2] n=int(input()) print(Catalan(n))

Input : 5 Output : 5

Complexity Analysis

Time Complexity: We need to perform N(N-1)/2 number of iterations to generate the Catalan series. Therefore the time complexity is of the order O(N^{2}).

Space Complexity: As we need a dp array of input size, the auxiliary space needed is of the order O(N).

FAQs

1). Brief about the complexity analysis of the above algorithm.

Answer:

Time Complexity - O(N^{2}) as there are N(N-1)/2 number of iterations.

Space Complexity - O(N) since the dp array created is of size N.

2). What would be the number of ways of triangulation in an 18 sided polygon?

Answer:

N=18

N-2=16

So there could be C_{16} ways of triangulation in an 18 sided polygon.

3). What is the formula for generating the n^{th} Catalan number?

We learned about the Catalan series and how it could be used to efficiently handle certain problems. The Catalan series can be used in a variety of problems and many of them are favourites among the recruiters. We recommend you to practice more such problems on our Coding platform Code Studio where we have problems straight from the interviews.