k-Sets, convex quadrilaterals, and the rectilinear crossing number of Kn*

József Balogh, Gelasio Salazar

Research output: Contribution to journalArticlepeer-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 D(S) of convex quadrilaterals determined by the points in S is at least 0.37553(4n) + O(n3). This in turn implies that the rectilineal crossing number cr̄(Kn) of the complete graph Kn is at least 0.37553 (4n) + O (n n), and that Sylvester's Four Point Problem Constant is at least 0.37553. These improved bounds refine results recently obtained by Ábrego and Fernández-Merchant and by Lovász, Vesztergombi, Wagner, and Welzl.

Original languageEnglish (US)
Pages (from-to)671-690
Number of pages20
JournalDiscrete and Computational Geometry
Volume35
Issue number4
DOIs
StatePublished - May 2006
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

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

Cite this