Lines Intersecting within a Polygon

Date: 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/