Triangulate square with $30$ distinct points inside square

Question

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?

Answer 1

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). $$