## Abstract

The so-called first selection lemma states the following: given any set P of n points in ℝ^{d}, there exists a point in ℝ^{d} contained in at least c_{d}n^{d+1}-O(n^{d}) simplices spanned by P, where the constant c_{d} depends on d. We present improved bounds on the first selection lemma in ℝ^{3}. In particular, we prove that c_{3}≥0. 00227, improving the previous best result of c_{3}≥0. 00162 by Wagner (On k-sets and applications. Ph. D. thesis, ETH Zurich, 2003). This makes progress, for the three-dimensional case, on the open problems of Bukh et al. (Stabbing simplices by points and flats. Discrete Comput. Geom., 2010) (where it is proven that c_{3}≤1/4^{4}≈0. 00390) and Boros and Füredi (The number of triangles covering the center of an n-set. Geom. Dedic. 17(1):69-77, 1984) (where the two-dimensional case was settled).

Original language | English (US) |
---|---|

Pages (from-to) | 637-644 |

Number of pages | 8 |

Journal | Discrete and Computational Geometry |

Volume | 44 |

Issue number | 3 |

DOIs | |

State | Published - 2010 |

## Keywords

- Centerpoint
- Selection lemma
- Simplex

## ASJC Scopus subject areas

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