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

Question

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?

Answer 1

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.

Answer 2

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\}$.

Answer 3

I'm not qualified to speak on this subject, but one cool think Ive found is that if you construct a regular polygon with n sides and extend the lines of those sides to infinity, you get that maximum number $\frac{n^2-n}2$ of intersections for odd $n$.

Repeating for even numbers we have $\frac{n^2-2n}2$ intersections, a difference of $\frac{n}2$ intersections.

So, for a polygon $n = \infty$ (a circle), you would get either $\infty$ OR $\frac{\infty}2$ intersections (its meaningless to talk about infinity as even or odd).

Therefore, this construction guaranteed to have as many intersections as possible.

Note: This construction is basically extending every tangent line of a circle to infinity, which I guess would be a solution to the system in an answer above which involved picking lines such that none are at the same angle and all have different positions.