Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Overview
1.1.
Example : 
2.
Approach
3.
How is the Catalan series helpful in handling this problem?
4.
Algorithm
4.1.
Implementation
4.2.
Complexity Analysis
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Number of ways of Triangulation

Author Arun Nawani
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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:-

 

C3 = C0*C2 + C1*C1 + C2*C0 = 1*2 + 1*1 + 2*1 = 5

C4 = C0*C3 + C1*C2 + C2*C1 + C3*C0 = 1*5 + 1*2 + 2*1 + 5*1 = 14

 

And so on.

 

  1. 1
  2. 1
  3. 2
  4. 5
  5. 14
  6. 42
  7. 132
  8. 429

….

 

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 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

  1. 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. 
  2. Initialise a dp array of size n to store the results of computations.
  3. Put dp[0] and dp[1] equal to 1. Iterate through the outer loop from i=2 to N.
  4. Iterate the inner loop from j=2 to i-1.
  5. Use the formula dp[i] += dp[j] x dp[i-j-1] in the nested loop to generate and store the catalan series.
  6. Print dp[n-2].

Implementation

def Triangulation(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
    forin range(2,n):
        forin 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?

Answer:

C= C0Cn-1 + C1Cn-2  + C2Cn-3 +....+ Cn-2C+ Cn-1C0

 

Key Takeaways

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. 

 

Previous article
Number of Ways to Convert 2 into N by Squaring, Adding 1, or Multiplying with 2
Next article
Count of non-decreasing Arrays C[] such that A[i] <= C[i] <= B[i]
Live masterclass