Document
Generically Dependent Continuant
RDF description of Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of Kn - http://orbis.uaslp.mx/vivo/individual/scopus8329
Article
Information Content Entity
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. © Springer-Verlag Berlin Heidelberg 2004.
Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of Kn
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) %2b O(n3). This in turn implies that the rectilinear crossing number ̄cr(Kn) of the complete graph Kn is at least 0.37553(4n) %2b O(n3). These improved bounds refine results recently obtained by Abrego and Fernández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl. © Springer-Verlag Berlin Heidelberg 2004.
Boundary conditions; Computer science; Mathematical models; Artificial intelligence; Computer science; Computers; Circular sequences; Convex quadrilaterals; Rectilinear crossing numbers; Graph theory; Drawing (graphics); Circular sequences; Complete graphs; Convex quadrilaterals; Lower bounds; Points in general position; Rectilinear crossing numbers
Conference Paper