Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of Kn

József Balogh, Gelasio Salazar

Research output: Contribution to journalConference articlepeer-review

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 languageEnglish (US)
Pages (from-to)25-35
Number of pages11
JournalLecture Notes in Computer Science
Volume3383
StatePublished - Dec 1 2004
Externally publishedYes
Event12th International Symposium on Graph Drawing, GD 2004 - New York, NY, United States
Duration: Sep 29 2004Oct 2 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of K<sub>n</sub>'. Together they form a unique fingerprint.

Cite this