## 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(_{4}^{n}) + O(n^{3}). This in turn implies that the rectilineal crossing number cr̄(K_{n}) of the complete graph K_{n} is at least 0.37553 (_{4}^{n}) + 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 language | English (US) |
---|---|

Pages (from-to) | 671-690 |

Number of pages | 20 |

Journal | Discrete and Computational Geometry |

Volume | 35 |

Issue number | 4 |

DOIs | |

State | Published - May 2006 |

Externally published | Yes |

## 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_{n}*'. Together they form a unique fingerprint.