Do you think IIT Guwahati certified course can help you in your career?
Problem Overview
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.
How is the Catalan series helpful in handling this problem?
We know C0=C1=1. For this scenario, let’s assume C2=C3=1 and the following series starts from C2 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 C0 as C2 and C1 as C3.
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 C4 = C2.C3 + C3.C2 in this case.
We know C4 = C0.C3 + C1.C2 + C2.C1 + C3.C0. But remember in this case our Catalan series begins with C2 instead of C0. So essentially C4 would be C2 in a regular Catalan series.
And as we saw earlier, a 5 sided polygon can be triangulated in 5 ways which are C3 ways.
Therefore it can be deduced that an N-sided polygon can be triangulated in CN-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 Cn-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(N2).
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(N2) 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 C16 ways of triangulation in an 18 sided polygon.
3). What is the formula for generating the nth 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.
84+ registered