# Improved Bounds for the Number of (<=k)-Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of K_n

Balogh, 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 29-October 2, 2004 , pp. 25-35(Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_4).

Full text not available from this repository.

## Abstract

We 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ández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl.

Item Type: Conference Paper 10.1007/978-3-540-31843-9_4 A General Literature > A.001 Introductory and Survey http://gdea.informatik.uni-koeln.de/id/eprint/564