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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.