# Minimal number of intersections in a convex $n$-gon?

For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all convex $n$-gons. (If three or more diagonals intersect at one point, we count it as a single point)

For example, $f(3) = 0$, $f(4) = 1$, $f(5) = 5$, but $f(6) = 13$ since there are only thirteen intersections in a regular hexagon.

Question: Is $f(n) \sim \frac{1}{24} n^4$? If not, then what is the asymptotic behavior of $f(n)$?

Comment 1. Obviously, $f(n) \le \binom{n}{4}$. On the other hand, it is possible to show that $f(n) \gt c n^4$ for an absolute constant $c \gt 0$ using the Szemerédi–Trotter theorem.

Comment 2. Poonen and Rubinstein proved that for a regular $n$-gon, the number of intersections made by its diagonals is $\frac{1}{24} n^4 + O(n^3)$.
("Number of Intersection Points Made by the Diagonals of a Regular Polygon." SIAM J. Disc. Math. 11, 135-156, 1998)

Edit 1. (August 17, 2015) In the comments, Boris Bukh suggested to consider the $n$-gon determined by the points $(i, i^2)$ for $-n/2 \le i \lt n/2$. Because I was unable to make a nice estimate in this case, I calculated them up to $n=200$. Here is the result.

The blue, orange, and green lines each represents the general case, the regular $n$-gon, and the parabola polygon; the values plotted are $(\# \text{ of intersection})/\binom{n}{4}$. This clearly shows that the parabola polygon has far less intersections compared to the regular $n$-gon. Still, the quotient increases after about $n=50$, and it might be heading towards $1$.

Subquestion: Is $(\# \text{ of intersections}) \sim \frac{1}{24} n^4$ for the parabola polygon?

• Did you compute the number of intersection points for the parabola (graph of $i\mapsto i^2$ on interval $[-n/2,n/2]$)? A cleaner problem might result if we replace "diagonal" by "lines spanned by vertices". – Boris Bukh Jul 26 '15 at 16:37
• @BorisBukh I would assume that this would be generic for the parabola (so $\binom{n}{4}$). – Igor Rivin Jul 26 '15 at 17:32
• @IgorRivin How do you see this without doing the calculation? – Boris Bukh Jul 26 '15 at 17:38
• Is there some case when the regular polygon does not give the minimal number of intersection points? – Per Alexandersson Jul 26 '15 at 21:47
• The numbers are tabulated at oeis.org/A230281 --- but only up to $n=8$. It seems $f(7)=29$ and $f(8)=49$. There are links to diagrams, and to articles (in Russian). $f(7)=29$ is illustrated at oeis.org/A230281/a230281.pdf – Gerry Myerson Jul 27 '15 at 6:35