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

### 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?

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 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/
```
Associated Topics:
High School Geometry
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