# Trianglify the Shapes

For each of the following shapes, draw extra lines to divide the shape into the smallest number of triangles that can completely fill the shape.

Example:

Solution:

Shapes (a correct answer answers all of these correctly, there is more than one and it is not divided into three questions to make this question more challenging):

• The blue shape is blue to increase visibility of what is inside and outside the shape (blue is inside).

## 1 Answer

Here is one possible triangulation.

Note that all triangulations (that do not introduce extra vertices) will have the same number of triangles, which depends only on the number of sides in the polygon.

A sketch of the proof: A polygon with three sides is already a triangle, so the minimal number of triangles needed to triangulate it is exactly $1$. For a polygon with $n$ sides, choose two adjacent sides and connect the two vertices they do not share with a line. This creates a triangle and a new polygon. The new polygon is missing the two sides we chose, but has an extra side (the new side we just created). Thus the number of triangles needed to triangulate a polygon with $n$ sides is $1$ plus the number of triangles needed to triangulate a polygon with $n-2+1=n-1$ sides. As a recurrence relation:

\begin{align} a(3) &= 1 \\ a(n) &= 1 + a(n-1) \\ \end{align}

Solving this yields $a(n) = n-2$, so the number of triangles needed to triangulate a polygon with $n$ sides is exactly $n-2$, regardless of that polygon's shape.

• Thing is - the 'that do no introduce extra vertices' is highly relevant. The math works, but only if you only allow for lines to be drawn between two existing corners. Some cases may have lower results if you do allow that. – Tim Couwelier Jan 4 '16 at 12:18
• @Tim I thought that adding a vertex would always add at least two triangles... could you give an example of the type of case you have in mind? – 2012rcampion Jan 4 '16 at 20:16