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 □(S) of convex quadrilaterals determined by the points in S is at least 0.37553(n4) + O(n3). This in turn implies that the rectilinear crossing number cr(Kn) of the complete graph Knis at least 0.37553(n4) + O(n3), and that Sylvester's Four Point Problem Constant is at least 0.37553. These improved bounds refine results recently obtained by Abrego and Fernandez-Merchant and by Lovasz, Vesztergombi, Wagner, and Welzl.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Balogh, J., Salazar, G. k-Sets, Convex Quadrilaterals, and the Rectilinear Crossing Number of Kn. Discrete Comput Geom 35, 671–690 (2006). https://doi.org/10.1007/s00454-005-1227-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-005-1227-6