Convex Quadrilaterals and k-Sets

Abstract

We prove that the minimum number of convex quadrilaterals determined by n points in general position in the plane ‐ or in other words, the rectilinear crossing number of the complete graph Kn ‐ is at least ( 3 + 10 ! 5 ) ! n + O(n 3 ). This is closely related to the rectilinear crossing number of complete graphs and to Sylvester’s Four Point Problem from the theory of geometric probabilities. As our main tool, we prove a lower bound on the number of (! k)-sets of the point set: for every k ! n/2, there are at least 3 ! k+1 2 subsets of size at most k that can be separated from their complement by a straight line.