TIFR CSE 2012 | Part A | Question: 4

Question

Let $\text{ABC}$ be a triangle with $\text{n} $ distinct points inside. A triangulation of $\text{ABC}$ with respect to the $\text{n}$ points is obtained by connecting as many points as possible, such that no more line segments can be added without intersecting other line segments. In other words $\text{ABC}$ has been partitioned into triangles with end points at the $\text{n}$ points or at the vertices $\text{A,B,C}$. For example, the following figure gives one possible triangulation of $\text{ABC}$ with two points inside it.

Although there are many different ways to triangulate $\text{ABC}$ with the $n$ points inside, the number of triangles depends only on $n$. In the above figure it is five. How many triangles are there in a triangulation of $\text{ABC}$ with $n$ points inside it?

• A. $3n - 1$
• B. $n^{2} + 1$
• C. $n + 3$
• D. $2n + 1$
• E. $4n - 3$

Comments

We can do this by eliminating the choices with the help of some examples

Answer 1

Any polygon can be split into triangles, so any $n\!-$triangulate for any $n$ will always be composed of triangles.

---

Given an $(n-1)$ triangulate, we can add the point in the following three ways:

1. The point lies on a point that is already there. In this case, the point has already been connected to all possible vertices that it can be connected to (since we started with a $(n-1)$ triangulate). Example:
   
2. The point lies on a line that is already there, but not on a point. In this case, since the line is the common edge of at most $2$ triangles, the point can only be connected to $2$ vertices (the opposite ends of the triangles). For example:
    
3. This creates $4$ new triangles, but destroys the original $2$ triangles. Thus, the number of triangles increase by $2$. This is an optimal case.
    
4. The point lies inside of a triangle. The new point can then be connected to exactly $3$ vertices of the bounding triangle. Example:
    
5. This creates $3$ new triangles, but destroys the original triangle. So, the number of triangles increase by $2$. So, this is also an optimal case.

---

We can see that the $n^{th}$ triangulate has exactly $2$ more triangles than the $(n-1)^{th}$ triangulate.
This gives us the following recurrence: $$T(n)=T(n−1)+2,T(2)=5$$

Which solves to: $$\boxed{T(n) = 2n + 1}$$

Hence, option d is the correct answer.

Comments

nice observation pragy.

Although it's hard that during exam time this way click our mind.Here in this question particularly we're lucky. We can easily see if n=1 then there would be 3 triangle in triangulation of original triangle. and only one option support this.

---

We can get only option d if we try triangulation using 3 , 4  points inside triangle.

For 3 points there are 7 triangles possible.

For 4 points there are 9 triangles possible.

Thus 2n + 1 is the answer.

---

Alternatively , select one point inside, you'd see that only three triangles are possible , others are not satisfied.