Say i have $n$ points in the plane all of which are connected with segment lines. What is the minimum number of intersections between the connecting lines?
Note 1: We count the number of intersections not intersection points, so even if three lines intersect in 1 point that's 3 intersections.
Note 2: There can not be 3 points in a line.
Here is the case for n=5 with one intersection.

enter image description here


You are trying to find the crossing number of the complete graph $K_n$. As you'll see in the link, the best upper bound on the crossing number is $$ \frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor. $$ It is known that the crossing number equals this upper bound for $n=5, 6, \ldots, 12$ and it is conjectured to hold for all $n \geq 5$.

  • $\begingroup$ That seems to be exactly what I was looking for. Is the upper bound rigorously proven though? $\endgroup$ – SoloNasus Aug 2 '16 at 14:32
  • $\begingroup$ Yes, the upper bound part has been proved $\endgroup$ – D Poole Aug 2 '16 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.