New lower bounds for the number of (<_K)- edges and the rectilinear crossing number of Kn
Oswin Aichholzer, Jesús García López de la Calle, David Orden, Pedro A. Ramos · 2006
We provide a new lower bound on the number of ( ≤ k)-edges of a set of n points in the plane in general position. We show that for 0 ≤ k ≤ ⌊ n−2 2 ⌋ the number of ( ≤ k)-edges is at least ( ) k ∑ k + 2 Ek(S) ≥ 3 + (3j − n + 3), 2 j= ⌊ n 3 ⌋ which, for k ≥ ⌊ n 3 ⌋, improves the previous best lower bound in [7]. As a main consequence, we obtain a new lower bound on the rectilinear crossing number of the complete graph or, in other words, on the minimum number of convex quadrilaterals determined by n points in the plane in general position. We show that the crossing number is at least