# How can you construct as many intersections as possible with n lines?

If you have $n$ lines, it seems to be obvious that you can have at most $\frac{n^2-n}{2}$ intersections:

$n = 1$: Obviously you need two lines to intersect, so the maximum number of intersections is 0

$n=2$: As one line can't intersect with itself, it can only intersect with the old lines. As there is only one line, you can get at most one intersection. So the maximum number of intersections of two lines is 1.

$n=3$: The same argument as before. The new line can only intersect with the two old lines and a given pair of two lines can intersect at most once. So you can get at most two new intersections. With the intersection of the two lines before, you get 3 intersections.

So the pattern is $\sum_{i=1}^{n-1} i = \frac{n^2-n}{2}$

But this only gives an upper border for the maximum number of intersections. I would now like to give a constrution where you can obviously see that you can get that many intersections.

I tried to make such an construction by hand:

but I guess with 10 lines this will get very confusing. Also, I don't know how to make it obvious that this construction can be continues indefinitely.

Do you know how you can construct as many intersections as possible with n lines?

-

If you choose $n$ lines randomly, they will intersect at $(n^2-n)/2$ different points almost surely.

More systematically: Choose $n$ directions for the $n$ lines such that no two lines are parallel. Then every line will intersect every other line, and you get $(n^2-n)/2$ points of intersection unless there happens to be some point where three or more lines intersect. So you need to choose the positions of the lines such that no three lines meet in the same point -- that is, for example, choose where each line intersects its normal through the origin (the direction of that normal is fixed once you have chosen the line itself, of course).

Place the lines one at a time. For each line you need to place it such that it avoids all of the crossing points between the lines you've already placed. However, at each point in the process there are only finitely many crossing points, which map to finitely many points on the normal-through-the-origin that must be avoided. But since the normal contains an infinity of points, there will always be points on it that you don't have to avoid, so just choose one of those.

-
I was thinking about line segments and not lines (I know, I wrote lines) which makes things more difficult at a first glance. But then I've realized that I can simply "cut" the lines after their last intersection and get line segments this way. – Martin Thoma Feb 4 '14 at 19:23

Here’s a concrete construction.

Let $L_k$ be the line with equation $y=kx+k^2$. $L_k$ and $L_m$ intersect at

$$p(k,m)=\langle-(k+m),-km\rangle\;.$$

Clearly $p(k,m)=p(r,s)$ iff $k+m=r+s$ and $km=rs$. However, on the line $x+y=a$ we have $xy=x(a-x)$, which as a function of $x$ is at most $2$-to-$1$, and clearly $p(k,m)=p(m,k)$, so either $r=k$ and $s=m$, or $r=m$ and $s=k$. Thus, $p(k,m)\ne p(r,s)$ whenever $\{k,m\}\ne\{r,s\}$.

-