Associated Topics || Dr. Math Home || Search Dr. Math

### Counting Intersections of Diagonals in Polygons

```
Date: 03/08/2000 at 11:19:55
From: Dominic Dingena
Subject: Intersections of Diagonals in Polygons

I tried to find an equation for the maximum number of intersections of
the diagonals in a polygon (because a polygon can have different
shapes, its diagonals may have different numbers of intersections, but
this is about the maximum number of intersections).

My equation is:

sqrt(D)*S^2
I = -----------
5

where D = number of diagonals, S = number of sides, and I = number of
intersections.

NOTE: This formula does not work for squares, triangles and pentagons.

What we have so far is:

Sides   Diag.s   Int.s
4       2         1
5       5         5
6       9        21
7      14        35
8      20        56
9      27        84
10      35       120
11      44       165
12      54       220

These numbers are in this number pattern:

1
1 2 1
1 3 3 1
etc.

My math teacher and I would really appreciate it if you would reply
```

```
Date: 03/08/2000 at 16:46:29
From: Doctor Peterson
Subject: Re: Intersections of Diagonals in Polygons

Hi, Dominic.

This is not an easy problem; I'd like to know more about how you are
approaching it. I get the impression you are just counting, making a
table, and looking for an apparent pattern; have you been looking for
what might be happening in the background that would produce whatever
patterns you see? That's where real mathematical thinking comes in. I
started by just looking for an orderly way to count, which gave me a
way to see patterns as they formed, and eventually found a formula
that will work for all polygons whose diagonals don't intersect more
than two at a time.

You might like to practice finding formulas by looking for the formula
for the number of diagonals in a polygon, if you haven't already done
so. There's a simple formula that you can prove by simple logical
reasoning, starting with the question, "How many ways can I make a
diagonal that ends at a given vertex?" This will give you D in terms
of S.

I checked out your table, and you must have made some errors in
copying it; for example, in line 3 you seem to have included the
vertices in the number of intersections, which should be 15, not 21.
For line 5 I get 70 intersections, and the rest are off too. In fact,
though your numbers are all in Pascal's triangle as you said, they
somehow switch from one line to another, hiding the real pattern. I'd
like to know how you went about counting these; were you careful not
to allow multiple intersections?

As for your formula, I can't see how it works; maybe I'm misreading
it. This doesn't seem to agree with your numbers at all, and in fact
in most cases the number of diagonals D is not a square, so the
formula doesn't even give a whole number. On your second line, for
example, S and D are both 5, and you would get sqrt(5)*25/5 = 11.18,
not 5. Can you explain where this formula came from, and how you are
using it?

Your observation that the numbers are in Pascal's triangle is good,
though you haven't said anything about where it is in the triangle or
why it should be so. Having found the correct numbers and seen that
they follow a particular diagonal of the triangle, I was able to find
a formula for I in terms of S alone, which gave the correct numbers.
Our FAQs on Pascal's triangle and on combinations may help you with
that:

Pascal's Triangle
http://mathforum.org/dr.math/faq/faq.pascal.triangle.html

Permutations and Combinations
http://mathforum.org/dr.math/faq/faq.comb.perm.html

Having seen a formula involving combinations, I was able to see a
reason why it should be true, without which I would really have no
grounds for claiming to have found a formula at all. (You can also use
the idea of combinations to find the number of diagonals.) If you
think about what it takes to form an intersection of diagonals
(namely, four endpoints to determine the two diagonals), you can
rather easily come up with my formula. But it took me a while to see
how easy it was.

anywhere I looked. The closest I came was in

The On-Line Encyclopedia of Integer Sequences
http://www.research.att.com/~njas/sequences/Seis.html

which gives a sequence of the number of actual intersections of a
REGULAR polygon, a much harder problem:

Name:      Number of intersections of diagonals of regular n-gon.

Sequence:  1, 5, 13, 35, 49, 126, 161, 330, 301, 715, 757, 1365, 1377,
2380, 1837, 3876, 3841, 5985, 5941, 8855, 7297, 12650,
12481, 17550, 17249, 23751, 16801, 31465, 30913, 40920,
40257, 52360, 46981, 66045, 64981, 82251, 80881, 101270

There is an attempt in our archives to solve this problem, which comes
close to the solution of your version of the problem, but doesn't
recognize the connection with Pascal and combinations:

Lines Intersecting within a Polygon
http://mathforum.org/dr.math/problems/loveland10.24.96.html

Keep working on this, and let me know when you come up with the
formula and an explanation for it. I'll be here if you need more help.

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Geometry
High School Permutations and Combinations
High School Triangles and Other Polygons

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search