Equation of line crossing

If you don't know where to post something, put it here and an administrator or moderator will move it to the right place.

Equation of line crossing

Postby elpenmaster » Tue May 17, 2005 6:37 am

Is there any equation for how many times lines can cross over each other if they have to be straight, and each one starts where the one before it ends, and the last line ends where the first line begins? To contruct this:

1. Draw a straight line.
2. Now, from where the first line ends, draw another sraght line to somewhere else.
3. Do this at least four times.
4. The last line that you draw has to end where the first one began.
5. Try to make any there be as many intersections between lines as possible.

The question is, is there a function that defines the maximum number of intersections y for the number of lines drawn x?

The domain is four and up.

The first few points are:
(4,1)
(5,5)
(6,7)
elpenmaster
Trionian
 
Posts: 157
Joined: Sat Feb 28, 2004 5:29 am
Location: Southern California

Postby jinydu » Tue May 17, 2005 6:48 am

I don't know of one. You could try using brute foce for a small number of lines, look for a pattern, and maybe try to prove it by induction.
jinydu
Tetronian
 
Posts: 721
Joined: Thu Jun 10, 2004 5:31 am

Postby houserichichi » Wed May 18, 2005 12:05 am

Is there any maximum number of intersections per point? That is, if two lines cross through a common point do you count that twice? I remember doing something like this in an old combinatorics class and I'm almost certain it had to do with triangular numbers, but I could be very off.
houserichichi
Tetronian
 
Posts: 590
Joined: Wed May 12, 2004 1:03 am
Location: Canada

Postby elpenmaster » Wed May 18, 2005 5:07 am

I found that while constructing, you can make no more than two lines intersect at one point by moving one line slightly over. so instead of having more than two lines cross at once, move the lines so it doesnt work out that way.
elpenmaster
Trionian
 
Posts: 157
Joined: Sat Feb 28, 2004 5:29 am
Location: Southern California

Postby elpenmaster » Thu May 19, 2005 4:56 am

As a correction, the domain can start at 3. The points i have found are:
(3,0)
(4,1)
(5,5)
(6,7)
(7,14)
(8,16)
(9,23)--i think

An interesting pattern is that the y values seem to come in grous of two that are two apart, but i dont know if that pattern holds up for larger x values.
elpenmaster
Trionian
 
Posts: 157
Joined: Sat Feb 28, 2004 5:29 am
Location: Southern California

Postby pat » Thu May 19, 2005 5:48 pm

Here's an absolute upper bound.

Extend each segment into a complete line. In the general case, each line will intersect each other line. Thus, if there are n lines, then each will intersect with (n-1) lines. So there are n(n-1)/2 crossings altogether (the factor of two is to make up for the fact that a crossing b is the same as b crossing a).

Now, since we're making connected segments and not counting the vertexes as crossings, we have to subtract out the n vertexes of the figure.

So, the result is n(n-1)/2 - n which is n(n-3)/2.

This can always be achieved for odd n. Draw a segment. Attach another segment. Draw the next segment to cross the first segment. Now, draw the next segment to intersect both of the first two. Draw the next segment to intersect the first three. Etc.

Now, for even n, you end up with a parity problem. If you continue as we did both the initial vertex and the last vertex end up on the same side of the third line (and third from the last line). So, you can't cross those lines and still hit the initial vertex.

I'm not sure how much of a restriction this is though.

But, I've also not been able to verify (8,16).
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Postby elpenmaster » Fri May 20, 2005 4:07 am

The equation x(x-3)/2 seems to work for odd x values. Using quadratic regression, an equation for even x values seems to be (3x^2-6x-16)/8, but that is only with the first 3. I checked (8,16) and it seemed work, unless a bigger number is possible.
elpenmaster
Trionian
 
Posts: 157
Joined: Sat Feb 28, 2004 5:29 am
Location: Southern California

Postby PWrong » Sat Jun 25, 2005 6:11 pm

Here's another way to get the maximum for odd n.

Draw a regular n-gon. Extend each line far enough so that it intersects with every other line, but no further. You get a star shaped figure with the maximum number of intersections.

This doesn't work for 6, but it does work for 8 for some reason. :?
User avatar
PWrong
Pentonian
 
Posts: 1599
Joined: Fri Jan 30, 2004 8:21 am
Location: Perth, Australia


Return to Where Should I Post This?

Who is online

Users browsing this forum: No registered users and 15 guests

cron