Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

I was surprised that I didn't find anything about this problem 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/