# Find the number of points at which the diagonals intersect

1. Nov 10, 2005

### vaishakh

In a convex-decagon, three diagonals are concurrent. From this information find the number of points at which the diagonals intersect with each other. Also find into how many regions is the polygon divided into by the diagonals?

At the first attempt to solve the question I tried with finding the number of diagonals. There are ten different point and each point can be joined with 9 other points. In this the segment joining the adjacent sides are the sides of polygon itself. Therefore the number of diagonal are 70 as they are 7 from each point. But the actual number should be 35, since in the found 70, for example AD and DA are different diagonals.
But now three diagonals, infact it can be assumed that only three diagonals are concurrent. The point of intersections of all other diagonals are distinct. I cannot frame a decagon to say at how many points should the diagonals intersect. Let the polygon is ABCDEFGHIJ, then diagonal like AD, GJ have no chance of intersecting with each other. But I cannot frame out which all diagonal can never intersect with each other and which all will.
Then started with small steps like diagonals AC, BD, CE, DF, EG, FH, GI, HJ, IA and JB will intersect at ten different points. The decagon if regular, will be divided into 16 regions. However I am not sure the number remains same even in the following condition also

2. Nov 10, 2005

### AKG

Let's look at something simpler. A quadrilateral has at most one point of intersection. A pentagon has 5. A hexagon has 15. Suppose an n-gon has D(n) diagonals. Then an n+1-gon has D(n)+n-1 diagonals. You can see this if you draw an n-gon, then see what happens when you add a point to make it an n+1-gon. Now if an n-gon intersects in I(n) points, you can again see that an n+1-gon intersects in I(n) + i(n) points, where:

$$i(n) = \sum _{k=1}^{n-2}k(n-k-1)$$

To see why this is, note that a diagonal XY in an m-gon separates the m-gon into two pieces, one of which will have j vertices (excluding X and Y) and the other will have m-j-2 vertices (excluding X and Y). This diagonal will intersect the other diagonals in j(m-j-2) points, so you see how we get I(n+1) if we know how many points of intersection we have from the diagonals of the n-gon, and then we add a new point and a bunch of new diagonals. Draw yourself some pictures and figure this out.

With the above, you will be able to find a closed form expression for the number of possible intesections for an n-gon. You will subtract 2 from I(10) because your decagon has 3 concurrent diagonals, so the three diagonals intersect at one point, whereas 3 diagonals could possibly give you 3 distinct points of intersection.

Now suppose you have an n-gon and you've drawn some diagonals, dividing your n-gon into R subregions. If you draw another diagonal which makes k intersections, you will make k+1 new subregions because you will split k+1 of the existing subregions each in half. Check this for yourself. So if an n-gon has R(n) regions, then you can figure out the number of regions of your n+1-gon by first adding a point outside your n-gon, and then connecting it with edges to two nearby vertices. This will have added one region. Next, you add n-2 diagonals. Each diagonal will make some intersections, and from the number of intersections you can find the number of additional subregions. This is related to the formula for i(n). Specifically, the number of extra subregions you'll get is:

$$\sum _{k=1}^{n-2}[k(n-k-1) + 1]$$

In total,

$$R(n+1) = R(n) + 1 + \sum _{k=1}^{n-2}[k(n-k-1) + 1]$$

Of course, these are for "ideal" shapes that have no concurrent diagonals. What I might do is let R'(5) be like R(5) but for a shape where three diagonals are concurrent. Figure out R'(5) by hand. Then you still have:

$$R'(n+1) = R'(n) + 1 + \sum _{k=1}^{n-2}[k(n-k-1) + 1]$$

so you can still solve for R'(10). All of the above was done in a bit of a rush, check it all for yourself.

3. Nov 12, 2005

### vaishakh

That post was indeed fantastic. My thought is in a bit different direction than of what you were. The numbers 1, 5 and 15 the number of points at which the diagonals of a quadirateral, pentagon and a hexagon meet recalled me of combination of 4, 5 and 6 things taken 4 at a time. I even have a logical support. An n-gon has n points, for a diagonal to exist there should be two points and for a intersection of diagonals atleast four points are needed. Therefore the maximum number of points at which the diagonals of a n-gon will intersect is the combination of n points taken four at a time.
Your R(n) formula seems to be correct. But I cannot produce any statements which support it. Further you gave the formula that if a diagonal intersect some other diagonals at k points then it adds up k+1 more subregions which even I could assume but that way finding each k is my main problem.

4. Nov 13, 2005

### AKG

Imagine a square with all its diagonals. Now add a triangle on top to make it look like a house. Treat your whole figure as a pentagon now. So far, you had R(4) regions plus the one you added (the triangle). So we have R(5) = R(4) + 1 + ________, and the _________ is because we still have more diagonals to add, namely the ones that will extend from our new vertex. Now you agree that a diagonal which intersects other diagonals at k points creates k+1 more regions, right? Imagine k vertical bars in a rectangle. They will divide the rectangle into k+1 regions, right? Now draw a horizontal bar across the rectangle, and it will split each of these regions into two, so you'll go from k+1 to 2(k+1), thereby adding k+1 regions. So, assuming we agree on this, then can you see how the _________ is related to the formula for i(n)?