Counting Crossroads: The Math of Intersections

Friday last week, I was talking with a friend on the train back home. The train just stopped in the middle of nowhere without any station in sight and we were thinking about what would cause this.

I said it probably had to do with scheduling. Sometimes trains have to stop so that other trains can pass or clear a section of track. It’s actually a matter of optimization. I argued that you can model the entire rail network as a mathematical problem where you try to minimize the total delay time, while respecting all the constraints of routes, stations, and train frequencies. Maybe this is something for another blogpost because optimization theory is another huge interest of me. My friend laughed when I said I might work on this in my spare time. Then I noted that knowing a bit of math can help you in a quiz, like the one I once did about how to see easily if a number is divisible by three.

And funnily enough, the following week I was actually preparing to host a quiz myself. I had already decided that it needed a good math question.

So today’s post is about that very quiz question. It starts simple. We just draw some straight roads on a map. How many times do they cross?

The problem Setup

So first, we have to properly define the problem. Let's consider that a road is an infinite straight line in the plane. We place roads randomly which comes down to:

• no two roads are parallel,
• no three roads pass through the same point.

The reasoning behind is that under any continuous random placement, these special cases occur with probability $0$. These special cases are so unlikely under random placement that, in a mathematical sense, they happen with probability zero, meaning they’re possible but so rare we can safely ignore them.

The question is, if we place the roads in this manner then how many intersections will be there? For two roads, the answer is simple. There is one intersection. For three roads the answer will be three. For four roads, there are six intersections. What is it for like seven roads? Let's try to find a pattern.

Recognizing A Pattern

If we draw the roads there are three additional crossing points above the present three crossing points. This is due to the fact that the new road crosses the present roads. Then what is the amount of crossing points for $N$ roads?

So if a new road is placed randomly then it will cross the $N$ present roads. This leads to $N$ additional crossing points on top of the already present crossing points. Denoting $P_{N+1}$ as the amount of crossing points for $N+1$ placed roads can be described as: $$ P_{N+1}=N+P_{N} $$ The important idea here is that

Each new road crosses all the existing ones exactly once, adding that many new intersections.

In the beginning there holds that $P_{1}=0$. Note that following this formula there also holds that $P_{2}=1, P_{3}=3$ and $P_{4}=6$ which aligns what we have said earlier. Now we come to the next question, is there a formula where we can easily find the amount of crossing points for $N$ roads?

And as a matter of fact, there is a formula. We just need to unwind the complete formula to its beginning. Let's try it for $N+1$ roads: $$ P_{N+1}=N+P_{N}=N+(N-1)+P_{N-1}=N+(N-1)+(N-2)+P_{N-2} = \cdots $$ $$ =N+(N-1)+(N-2)+\cdots+3+2+1=\sum_{k=1}^{N} k=\frac{N(N+1)}{2} $$ However, this is nothing more than the iconic formula Gauss came up with. We have also discussed its full derivation in another blogpost. Now applying the formula for $N$ roads gives: $$ P_{N}=\sum_{k=1}^{N-1} k=\frac{N(N-1)}{2} $$ This formula appears quite often in mathematics. It’s not only the number of ways that $N$ different roads can intersect, but also has a link to the number of items you can arrange in an equilateral triangle. Imagine you’re stacking logs or cannonballs in rows. You start with one log on top, then a row of two beneath it, then three, and so on.

You’ll quickly notice that you can only make a perfect triangular pile if the total number of logs is $1, 3, 6, 10, 15,$ and so on. These numbers $1, 3, 6, 10,$ … are called the triangular numbers. You can visualize this as the total number of dots needed to fill a triangle with $N$ rows. The pattern is the same as the road crossing. $$ T_1 = 1,\quad T_2 = 3 = 1 + 2,\quad T_3 = 6 = 1 + 2 + 3,\quad T_4 = 10 = 1 + 2 + 3 + 4,\ \dots $$ Each new row adds one more than the previous. The $N$th triangular number $T_N$ is thus the sum $$ T_N = 1 + 2 + \cdots + N = \frac{N(N+1)}{2}. $$

Alternative Viewpoints

Personally, I think this is a very nice result. Why? Well, there are other ways of viewing it. Whenever two roads cross an intersection appears. Each intersection is made by exactly two roads meeting. If we take all the roads we’ve drawn, every possible pair of them will cross once because we assumed no two roads are parallel and no three meet in the same spot. So, instead of literally drawing and counting all the crossings, we can simply ask:

How many different pairs of $N$ roads can we form?

So in essence, it just comes down to the following: $$ \text {# intersections }=\text{#} \text { subsets of size } 2 \text{ in a population of } N=\binom{N}{2} $$ The story is just the same as if you were to look for the number of handshakes a group of $N$ people would exchange among themselves. Pick two people uniformly at random from this group of $N$ people. The number of possible unique pairs is $\binom{N}{2}$. This is the same combinatorial count as the road problem, because an intersection corresponds to "choosing which two roads meet at that point," just as selecting a pair of people corresponds to "choosing which two persons will handshake." $$ \text {# intersections among } N \text { roads }= \text {# combinations of } 2 \text{ persons from } N \text { people }=\binom{N}{2} $$ If you are not satisfied with this explanation then you could also view it in the following way. Pick one person from the group of $N$ persons. Then pick one person of the remaining group of $N-1$ persons. This means that there are in total $N(N-1)$ handshakes possible. However, person $A$ can give a handshake to person $B$ and a person $B$ can give a handshake to person $A$. This means that we have not accounted for this double redundancy. Dividing by 2 leads to $\frac{N(N-1)}{2}=\binom{N}{2}$.

What about the edge cases we did not discuss before? Well, what we found was a strict upper bound for the amount of crossing points. If we allow parallel roads and/or more than three roads crossing in the same point then there will hold that $P_{N} \leq\binom{ N}{2}$. However, if we randomly place roads throughout the space then both these effects will occur with probability zero. So the expected number of intersections is $\binom{N}{2}$.

Conclusion

In conclusion, the recurrence formula $P_{N+1}=N+P_{N}, P_{1}=0$ packages a simple geometric fact by encoding that each new road meets all previous ones once. Combinatorially, it's the same count as how many ways to choose two people from a group of $N$. So in essence, counting intersections is the same as counting how many pairs of roads you can form. It's just like counting how many handshakes can happen among $N$ people.

This is just another beautiful illustration of how such a simple setup, roads crossing on a map, connects geometry, combinatorics, and even probability theory. Mathematics is full of these unexpected connections. Simple questions like these show that beauty in math often hides in plain sight.