TY - JOUR
T1 - Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of Kn
AU - Balogh, József
AU - Salazar, Gelasio
PY - 2004/12/1
Y1 - 2004/12/1
N2 - 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(4n) + O(n3). This in turn implies that the rectilinear crossing number ̄cr(Kn) of the complete graph Kn is at least 0.37553(4n) + O(n3). These improved bounds refine results recently obtained by Abrego and Fernández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl.
AB - 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(4n) + O(n3). This in turn implies that the rectilinear crossing number ̄cr(Kn) of the complete graph Kn is at least 0.37553(4n) + O(n3). These improved bounds refine results recently obtained by Abrego and Fernández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl.
UR - http://www.scopus.com/inward/record.url?scp=24144482643&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=24144482643&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:24144482643
VL - 3383
SP - 25
EP - 35
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SN - 0302-9743
T2 - 12th International Symposium on Graph Drawing, GD 2004
Y2 - 29 September 2004 through 2 October 2004
ER -