24
$\begingroup$

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. $\# intersections /\binom{n}{4}$ for $n \le 200$

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?

$\endgroup$
  • 4
    $\begingroup$ 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". $\endgroup$ – Boris Bukh Jul 26 '15 at 16:37
  • $\begingroup$ @BorisBukh I would assume that this would be generic for the parabola (so $\binom{n}{4}$). $\endgroup$ – Igor Rivin Jul 26 '15 at 17:32
  • $\begingroup$ @IgorRivin How do you see this without doing the calculation? $\endgroup$ – Boris Bukh Jul 26 '15 at 17:38
  • 2
    $\begingroup$ Is there some case when the regular polygon does not give the minimal number of intersection points? $\endgroup$ – Per Alexandersson Jul 26 '15 at 21:47
  • 7
    $\begingroup$ 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 $\endgroup$ – Gerry Myerson Jul 27 '15 at 6:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.