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(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.
Original language | English (US) |
---|---|
Pages (from-to) | 25-35 |
Number of pages | 11 |
Journal | Lecture Notes in Computer Science |
Volume | 3383 |
State | Published - 2004 |
Externally published | Yes |
Event | 12th International Symposium on Graph Drawing, GD 2004 - New York, NY, United States Duration: Sep 29 2004 → Oct 2 2004 |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science