The largest number of intersection points we can obtain from $10$ distinct points on a circle.

Question

Suppose we pick $10$ distinct points on a circle and connect all pairs of points with line segments, what is the largest number of intersection points we can obtain?

---

I have tried with $4$ points and got $1$ intersection point.

Next, I have tried with $5$ points and got $5$ intersection points.

Finally, I have tried with $6$ points and got $15$ intersection points.

---

After that I am lost. Can someone give an argument how to find it?

Answer 1

Pick any arrangement of the $n$ points that you like, choose $4$ points out of these $n$ points, call them $A,B,C,D$ and lets say that they have a circular order so if you start, say, on the top of the circle going clockwise you hit the points in lexicographic order.

Is it true that they form exactly one intersecting point? If so, then the problem boils down to finding how many $4$ points you can choose out of $n$ points, so $\binom{n}{4}.$

This if you can guarantee that you could have find an arrangement in such a way that two intersecting points are not the same intersecting point.

Answer 2

To explain how the process will work, we'll make quadrilaterals whose points are always ordered in a circle. That is, $ABCD$ is a quadrilateral where $A$ is on the left of $B$, $B$ is on the left of $C$, $C$ is on the left of $D$, and $D$ is on the left of $A$. Also, there must be $n \geq 4$ points.

We can make the diagonals $AC$ and $BD$. Notice that they always have an intersection point. This means that for each quadrilateral, there must be one intersection point, changing the problem to counting the number of quadrilaterals that we can make.

Since quadrilaterals are made up of four points, we can choose four points without order, giving us $\binom{n}{4}$.

Is this the maximum? It is, assuming that no two lines intersect at the same point. Otherwise, we are overcounting. See the case where the points form a regular polygon, for instance.

---

Edit:

Why not choose pairs of lines instead of points? We can, but the problem is, the intersection of these lines may be outside the circle.

Let $P(\theta) = (\cos\theta, \sin\theta)$. That is, given an angle $\theta$, $P(\theta)$ will give us the point in the unit circle.

Now, let $P_n = P(\frac{n}{2}\pi)$ for $n = \{1, 2, 3\}$ and let $P_4 = P(-\pi/4)$. By choosing four points to make a quadrilateral and getting the intersection of the diagonals, we can see that it will lie at $(-1+\sqrt{2}, 0)$. By choosing pairs of lines and finding the intersections, we can see that:

1. Only one of these points is inside the circle and this is the intersection point we found from the four points method,
2. Four of these points lie in the circumference of the circle. This is when two lines shared a point.
3. The remaining two points are outside the circle.

Although it is valid that the points on the circumference are intersections, these points are we don't need, especially the points outside the circle. Hence, the $\binom{n}{4}$ will be our formula, if we what we are counting are points inside the circle only. Points on the circumference and outside the circle are excluded.

If you wish to include the points outside, then $\binom{n}{4}$ will undercount the points and you need to work on the $\binom{\ell}{2}$ formula where $\ell$ is the number of lines made from the $n$ points where $\ell = \binom{n}{2}$. In this case, you might want to remove some duplicates as intersections of two pairs might not be distinct.

Answer 3

Notice how every intersection point results from $4$ distinct points. In other words, they are the diagonals of a quadrilateral that the $4$ points make.

Therefore, we can find the number of intersection points where there are $n$ points by $n\choose4$.

So, if there are $10$ points on the circle, then the number of intersections can be given by ${10\choose4} = \boxed{210}.$