Improved Bounds for the Number of (<=k)Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K_nBalogh, József and Salazar, Gelasio (2004) Improved Bounds for the Number of (<=k)Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K_n. In: Graph Drawing 12th International Symposium, GD 2004, September 29October 2, 2004 , pp. 2535(Official URL: http://dx.doi.org/10.1007/9783540318439_4). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540318439_4
AbstractWe use circular sequences to give an improved lower bound on the minimum number of (<=k)sets in a set of points in general position. We then use this to show that if S is a set of n points in general position, then the number $\square(S)$ of convex quadrilaterals determined by the points in S is at least $0.37553\binom{n}{4} + O(n^3)$. This in turn implies that the rectilinear crossing number $\overline{\hbox{\rm cr}}(K_n)$ of the complete graph K_n is at least $0.37553\binom{n}{4} + O(n^3)$. These improved bounds refine results recently obtained by Ábrego and FernándezMerchant, and by Lovász, Vesztergombi, Wagner and Welzl.
Actions (login required)
