2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Use that Faces(number of triangles plus the exterior of the square)${}-{}$Edges${}+{}$Vertices$=2$. $\endgroup$ – OR. Mar 28 '14 at 0:52
  • $\begingroup$ 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? $\endgroup$ – Kevin Mar 28 '14 at 0:55
  • $\begingroup$ 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$. $\endgroup$ – OR. Mar 28 '14 at 0:55
  • $\begingroup$ 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. $\endgroup$ – Kevin Mar 28 '14 at 1:06
  • $\begingroup$ 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. $\endgroup$ – Kevin Mar 28 '14 at 1:18
1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – chubakueno Mar 28 '14 at 4:27
  • $\begingroup$ Oops, yeah at first I wrote 34 points, then someone edited it to 29, so now I changed it to 30. $\endgroup$ – Kevin Mar 29 '14 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.