Any fool can write code that a computer can understand. Good programmers write code that humans can understand.
~ Martin Fowler
Number of Ways of Triangulation
Welcome back, dear reader. So, how is it going? Today we will
discuss another interesting problem called the NUMBER OF WAYS OF
TRIANGULATION. So, what does this problem say?
By triangulation, we mean that partition the polygon in such a way that each part is a triangle, and the lines we draw to triangulate it must have their endpoints on the vertices of the polygon only. We recommend you refer to the Number of Ways of Triangulation video to understand the question if you have any doubts regarding it. We recommend you try to solve this problem on your own first and then refer to the solution to make your concepts strong.
We are given an input N which represents the number of sides of a polygon. We have to tell the number of ways in which it can be triangulated. For instance, if N=5, the shape is a pentagon and it can be triangulated in 5 ways as shown below:
Approach:
Time Complexity:
O(n2) where n is the number of sides of the polygon that we have to triangulate.
Space Complexity:
O(n)
Approach:
The number of ways in which we can triangulate a polygon of sides N is the (N-2)th Catalan number. So, we just have to find the (N-2)th Catalan Number. The algorithm to find Nth Catalan number is given below
Create a dp array of size n+1 where n is the input Catalan number.
Fill dp[0]=1 and dp[1]=1 and then start the outer loop from i=2 to i=n.
Start the inner loop from j=0 to less than I i.e. j=0 to j < i.
Use the formula dp[i] += dp[j] x dp[i-j-1] inside the inner loop to fill the array with the Catalan numbers.
Print dp[n] as the answer.
Explanation:
What of the Problem
The "what" of the problem is simple. We will generate (N-2)th Catalan Number and this will be the number of ways in which we can triangulate a polygon of N sides.
Why of the Problem
Let us now try to find the "why" of the problem i.e. why the (N-2)th Catalan Number gives us our answer. Let us take different input values and try to analyze the number of ways in which we can triangulate a polygon having N sides.
When N=0 or N=1 or N=2
When the input value of N is less than 3, our answer will be 0. This is because we cannot triangulate a shape with less than three sides.
The minimum sized polygon is a triangle and we need three sides for it. So, if we are given less than three sides, the shape is not even a polygon and we cannot triangulate it.
You might think that we can triangulate a shape of 2 sides as shown below
We cannot triangulate a figure which is not a polygon as the question is about triangulating a polygon only. Hence this triangulation is not valid and the number of ways of triangulating an N-sided figure when N < 3 is 0.
When N=3
When N=3, the given polygon is a triangle itself. So, there is only one way to triangulate it, do not do anything with the polygon. You might be thinking that we can triangulate this polygon also in the way as shown:
We can't do this because of the reason mentioned in the diagram only.
Assumption
Till now we have discussed what you can call the base cases i.e. the inputs for which we do not need to calculate any answer. Now, before we move forward, we want to change our method of thinking a little bit. See, when we talk about a 3-sided or a 4-sided or a 5-sided polygon and so on, we will notice that the number of vertices and edges of these shapes are equal.
For instance, a triangle has 3 vertices and three edges and a quadrilateral has 4 vertices and 4 edges, and so on. So, first of all, we will now replace the sides with vertices i.e. we will now stop thinking of the solution keeping the sides in our mind. Now, we will talk about the N-vertexed polygons rather than N-sided polygons.
Also, we will assume that we have one way to create a triangle if the number of vertices given to us is 2. If the number of vertices is 2, we have only one straight line. So, we are assuming that there is a way to triangulate this figure where the third point lies on the line itself. We can call this a triangle of size 0.
Note: Please note that this is just an assumption to make our work easier for further cases. We know that this does not make much sense now to you, but it will when we move forward. Also, whenever we get an input N < 3, we will print 0 only. This assumption is being done so that we can derive the answer for the next upcoming cases.
When n=4: When n=4, we have 2 ways to triangulate it as shown in the figure below:
Let us verify also that there are only 2 ways to triangulate a 4-vertex polygon. So, we will first join vertex 1 and 2 and make a triangle T1(1,3,4).
Towards the left of the triangle T1, we can see that there are 2 points on the base and we can see 3 points on its right.
So, the number of ways in which we can triangulate the quadrilateral if we join the points 1 and 4 is the number of ways of triangulation of 2-vertex polygon multiplied by the number of ways of triangulation of 3-vertex polygon. We know that a 3vertex polygon can be triangulated in 1 way and a 2-vertex polygon is assumed to be triangulated in 1 way too. So, we get the answer 1 x 1=1 i.e. the only way shown already in the image above.
The same will be the case for the second quadrilateral and the total answer will be 1+1=2.
Catalan and Triangulation Comparison
We have calculated the triangulation of a 4-vertex polygon as shown in the image below:
Also, triangulation of 2-vertex polygon and triangulation of 3-vertex polygon is 1 and 1. If we look at the Calculation of the 2nd Catalan number it looks like this:
This looks the same. So, we can say that the number of ways of triangulation of a 2-vertex polygon is the same as the 0th Catalan number and the number of ways of triangulation of a 3-vertex polygon is the same as the 1st Catalan number and so on.
So, the number of ways of triangulation of an N-vertex (N-sided) polygon (when N>3) is the (N-2)th Catalan number
Let us try this on a pentagon too so that we can be sure of this conclusion and also understand the concept in more detail and depth.
When n=5: Firstly, we can have three figures to start with as shown in the image below:
Let us start with the first figure. We can see that it has 2 points on the left and 4 points to the right. So, the number of ways in which it can be triangulated is as shown below:
Now, let us calculate the number of ways of triangulation of the second figure in above image.
The third figure in the same figure is similar to the first figure.
So, when N=5, the answer comes out to be 5.
So, the number of ways in which we can triangulate a polygon of sides 5 is the 3rd Catalan number.
We hope that you have now understood how we concluded that the number of ways of triangulation of an N-sided polygon when N>2 is the (N-2)th Catalan number.
We recommend you refer to the solution video to understand the above-explained part of the article and also see the derivation of this proof for a hexagon. This hexagon example is quite long so we couldn't cover it here but it is covered in-depth in the video and it will build your insight into this concept up to some unimaginable level.
Now that we have covered everything, let us write the code for this problem.
Code
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
System.out.println(solution(n));
}
public static int solution(int n){
if(n < 3){ // there are 0 ways for triangulating shapes with less than 3 sides
return 0;
}
int[] dp = new int[n - 1]; //because if n=5, size will be 4 and last index will be 3
// so we will get Catalan of 3 i.e. catalan of n-2
dp[0] = dp[1] = 1; // 1 way for 2-vertex and 3-vertex shape triangulation
for(int i = 2; i < dp.length; i++){
for(int j = 0 ; j < i; j++){
dp[i] += dp[j] * dp[i - j - 1];
}
}
return dp[dp.length - 1]; ///This will give triangulation of n sides= Catalan of n-2.
}
}
We recommend you refer to the solution videoto understand the code. Now, let us discuss the time and space complexity of the above code.
java;
true";
Time and Space Complexity Analysis
Time Complexity:
The time complexity of the above solution is O(n2) where n is the input number as the inner loop runs for n(n-1)/2 times. This makes the complexity O(n2).
Space Complexity:
The space complexity is O(n) as we make an array of size n-1.
So, dear reader, we hope that you got the time and space complexity as well. We recommend you refer to the complete solution video once to clear all your doubts if any. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
We suggest you watch the complete solution video once as this will give you a very deep insight into the problem and how we can break down the problem into Catalan Number Problems. This is a very interesting collection of questions that we are doing right now. This will increase your thinking skills and approach towards a problem. So, keep practicing and working hard. Till then, Happy Coding!!!