Let there be a convex polygon $P$ with $n$ vertices, $P_1, \dots, P_n$. Let us add $k$ distinct line segments to this polygon $\overline{P_{a_i}P_{b_i}}$ such that $P_{a_i}$ and $P_{b_i}$ are vertices on the polygon and $|{a_i - b_i}| \neq 1, |a_i-b_i| \neq n-1$ (in other words, the line segments we add are distinct diagonals of the polygon).
My question is this: say we choose the $k$ line segments optimally so as to minimise the number of pairs of line segments that intersect. What is the minimum number of intersections we can get?
I can see that for $k \leq n-3$, the minimum possible number of intersections is $0$. I am interested in how the number grows for $k > n-3$, either closed-form or even asymptotics. My guess is that the asymptotic number of intersection is $ck^2$ for constant $c$ but I don't know how to prove it.