# Triangulate square with $30$ distinct points inside square

Let $A_1A_2A_3A_4$ be a square, and let $A_5,A_6,A_7,\ldots,A_{34}$ be distinct points inside the square. Non-intersecting segments $\overline{A_iA_j}$ are drawn for various pairs $(i,j)$ with $1\le i,j\le 34$, such that the square is dissected into triangles. Assume each $A_i$ is an endpoint of at least one of the drawn segments. How many triangles are formed?

• Use that Faces(number of triangles plus the exterior of the square)${}-{}$Edges${}+{}$Vertices$=2$. – OR. Mar 28 '14 at 0:52
• So I know there are 34 points (since 1-34) so those are my vertices. But how many edges are formed? Any method in finding this? – Kevin Mar 28 '14 at 0:55
• Notice that the number of edges can be put as a function of the faces, since each triangle has three edges and edges interior to the square are shared by two triangles. I am assuming none of the points lie on a side of the square. So, I guess Edges${}={}3$Faces${}-{}4$, divided by $2$ (because the remaining edges are shared by two triangles), and then plus $4$ again. $E=(3F-4)/2+4$. – OR. Mar 28 '14 at 0:55
• Would this be a valid picture of the triangulation? picture If it is, I might either use your formula or count it out... Yeah, probably the formula. EDIT: I used your formula and V+F-E=2, and got F=60. Subtract 1 for 'infinity face' to get 59, but that's not the right answer. – Kevin Mar 28 '14 at 1:06
• Lol, actually my picture was correct. The answer was 62, and when I counted it out on my picture, I got the right answer! Thanks anyways. It still would be nice to get a "legitimate" solution though. – Kevin Mar 28 '14 at 1:18

There seems to be a problem with your statement. You say you want the triangularization of the square with 29 distinct interior points, but the list $A_5,\ldots, A_{34}$ Acually has $34-5+1=30$ points?

In any event, if you triangularize a triangle then the relationship between $F$ and $E$ is $$3F=2E.$$ This is because each face is a triangle which uses 3 edges and each edge is in exactly 2 triangles.

We can extend this to the triangularization of a square by observing all but one of the regions is a triangle, so $$3F+1=2E.$$

Assuming 29 interior points we have $$F-E+V=2\,\Longleftrightarrow\, F-\frac{3F+1}{2}+33=2\,\Longleftrightarrow\,\frac{-F-1}{2}=-31\,\Longleftrightarrow\,F=61.$$

Assuming 30 interior points we have $$F-E+V=2\,\Longleftrightarrow\, F-\frac{3F+1}{2}+34=2\,\Longleftrightarrow\,\frac{-F-1}{2}=-32\,\Longleftrightarrow\,F=63.$$

Since our $F$ also counts the exterior (a square region), we need to reduce our values by $1$ to count the triangles. Thus there are 60 triangles with 29 interior points and 62 triangles with 30 interior points.

In general, the number of triangles in the triangularization of a square with $n$ interior points, $t(n)$, is given by $$t(n)=2(n+1).$$

• We can also see it this way: When there is no points inside the square, we start with two triangles and each time we add a point we split one triangle into three, effectively adding two triangles per point. – chubakueno Mar 28 '14 at 4:27
• Oops, yeah at first I wrote 34 points, then someone edited it to 29, so now I changed it to 30. – Kevin Mar 29 '14 at 20:09