32
$\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?

Improve this question
$\endgroup$
9
  • 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
    Commented Jul 26, 2015 at 16:37
  • $\begingroup$ @BorisBukh I would assume that this would be generic for the parabola (so $\binom{n}{4}$). $\endgroup$
    – Igor Rivin
    Commented Jul 26, 2015 at 17:32
  • $\begingroup$ @IgorRivin How do you see this without doing the calculation? $\endgroup$
    – Boris Bukh
    Commented Jul 26, 2015 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
    Commented Jul 26, 2015 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
    Commented Jul 27, 2015 at 6:35

0

Reset to default

You must log in to answer this question.