Lines Intersecting within a PolygonDate: 10/24/96 at 18:12:24 From: Keith Loveland Subject: geometry A fellow math teacher asked me this the other day: Given an n-sided regular polygon with each vertex connected to each other vertex by a straight line segment, how do you determine the number of intersection points within the polygon? I tried n = 3 through n = 8, looked for a pattern, and noticed some things but nothing definitive. I plotted these points with the intersection points as a function of n and tried curve fitting, but couldn't get an exact fit. Do you know a rule for this? Is there an odd and even set of rules? Thanks for any help you're able to give me, Keith Loveland Date: 10/24/96 at 20:48:14 From: Doctor Tom Subject: Re: geometry Hi Keith, Well, this isn't a complete answer, but it may help some. I can solve the problem if the points are "unevenly" spaced around the polygon, but not if they're evenly spaced. What I mean is this - I can count the number of times pairs of lines cross each other, but the simplest case where this goes bad is the perfect hexagon. Three lines go through the center, and if those are called lines A, B, and C, then my method counts AB, BC, and CA as three points when it probably should be counted as one. Notice that if the vertices are moved just a little, instead of hitting at a single point, there would be a tiny triangle with 3 intersections. As the number of lines goes up, the number of these multiple intersections increases, and in a funny way that has to do with the prime factorization of the numbers. My formula should work exactly for all prime-sided polygons, for example. Here's how I did it: For a triangle, there are no intersections. For a square connecting points 1,2,3,4, break it into two parts: those involving a line from 1, and those not involving a line from 1. Those not involving a line from 1 include all the crossings made by the triangle 234: zero to be exact. Those involving a line from 1 include 13 crossing 24, or one intersection. So for a square, there is 1 total. I'll jump up a bit so you can see more easily, I think, what's going on. Consider a 7-sided polygon 1,2,3,4,5,6,7. Suppose you've got the crossing number for the 6 sided 2,3,4,5,6,7, and you just need to count the number of lines involving point 1. If 1 connects to 4, those crossing it must connect 2 or 3 with 5, 6, or 7. If 1 connects to 3, those crossing it must connect 2 with 4, 5, 6, or 7, and so on. If 1 connects to 2, nothing crosses it. So consider all the lines starting from 1: 1-2: nothing 0 ways 1-3: {2} to {4,5,6,7} 1x4 ways 1-4: {2,3} to {5,6,7} 2x3 ways 1-5: {2,3,4} to {6,7} 3x2 ways 1-6: {2,3,4,5} to {7} 4x1 ways 1-7: nothing 0 ways So the answer is whatever your answer for 6 was plus 1x4+2x3+3x2+4x1. So here's the full method, where f(n) is the number of ways to do this with n points: f(3) = 0 f(4) = f(3) + 1x1 = 0 + 1 = 1 f(5) = f(4) + 1x2 + 2x1 = 1 + 2 + 2 = 5 f(6) = f(5) + 1x3 + 2x2 + 3x1 = 5 + 3 + 4 + 3 = 15 f(7) = f(6) + 1x4 + 2x3 + 3x2 + 4x1 = 15 + 4 + 6 + 6 + 4 = 35 et cetera. My intuition tells me that these numbers will satisfy a fourth-power equation (I am 99% sure of this for reasons that I can't explain). So if you work out a few more terms for f(8), f(9), and so on, and then imagine that the solution must look like this: f(n) = A*n^4 + B*n^3 + C*n^2 + D*n + E Plug in n = 3, 4, 5, 6, 7, and consider A, B, C, D, and E to be unknowns, you'll get 5 equations in 5 unknowns, and you can work out A, B, C, D, and E. But as I said, I have no idea how to take into account the multiple crossings. Good luck. -Doctor Tom, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/